Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

C11TCT - Xông đất ngày Tết

Bò đi xông đất vào ngày Tết. Khu phố nơi Bò ở có m ngôi nhà, Bò muốn xông đất đúng n ngôi nhà. Tuy nhiên Bò lại muốn xông đất sao cho không có 2 ngôi nhà nào kề nhau. Hỏi: Có bao nhiêu cách để xông đất thỏa mãn?

Kết quả theo module 100003 (10^5 + 3)

Input

Dòng đầu là số nguyên T (số test, T <= 10^5).

Mỗi dòng trong T dòng sau chứa 2 số nguyên m và n (1 <= m, n <= 10^16)

Output

Gồm T dòng, mỗi dòng là số cách tương ứng với từng test.

Example

Input:
2
5 2
5 3

Output:
6
1

Được gửi lên bởi:Nguyễn Duy Khánh
Ngày:2015-02-27
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:Trên trời rơi xuống

hide comments
2017-10-03 06:04:46
có ai sai test 10 và sửa lại được chưa ạ???
2015-08-16 09:55:15 Phong


Last edit: 2015-08-16 10:02:27
2015-03-25 16:18:53 Dương Bảo
sao cứ đến test 10 là WA :'(
2015-03-09 07:32:00 Cedrus
10^16 @@
2015-03-04 15:15:50 Ðặng Phương Tân
Bài này có cách nào giải không mọi người :((
2015-02-28 13:04:16 Trần Quang Linh
:v
2015-02-27 17:28:14 Sue
bò đi xông đất :v

Last edit: 2015-02-27 17:31:07
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.