Secret Meeting

mehdi_ IUT 8th ICT Fest Programm...
Limits 2s, 512 MB

The world is terrified by Pandas! After a miraculous chemical explosion, they became smarter; and eventually they are trying to take control! Today, Pandas around the globe are gathered in a secret meeting! In the meeting they are sitting around circular tables. Two properties hold for their sitting arrangement:

  • Pandas from same region are sitting in same table.
  • For each Panda, adjacent Pandas in the circular table are its closest friends!

Now, at each table i, N_i Pandas are sitting, and as ordered by higher authority, from each table K_i Pandas must be chosen for the next covert plans. Why? Well, nobody knows that reason! However, one property holds for the selection:

  • If a Panda is selected, then any of its closest friends can’t get selected.

Meanwhile, the anti-Panda squads are not just passing time! But they need to know the value of a specific number to stop the covert ops. Given the lists of integer values N_i andK_i, they need the sum of possible number of ways to select K_i Pandas from N_i of them, over all i.

Consider, N_i as, i subscript of N. It’s just to denote the i’th term of a list of integer values. See explanation if you are not clear.

Input

The first line will contain an integer Q (0 < Q <= 10^5), and the next Q lines will contain two integers denoting N_i and K_i, respectively. Here 0 < K_i, N_i <= 2 × 10^7.

Output

Output just a single line containing the required value modulo 103003811.

Samples

InputOutput
2
5 2
5 2
10
InputOutput
3
15 5
12 3
12 5
526
InputOutput
1
50 7
37469900

For the first sample, there are two tables, 5 Pandas sitting around each. From each table 2 Pandas must be chosen, it can be chosen in 5 ways: (1,3), (1,4), (2,4), (2,5) and (3,5). So the required value will be 5+5 = 10.

Submit

Login to submit.

Statistics

90% Solution Ratio
iutictf8.82$b30nEEarliest, Nov '16
tuhin107494Fastest, 0.1s
KnightMareLightest, 6.2 MB
iutictf8.20$wLqMQShortest, 1598B
Toph uses cookies. By continuing you agree to our Cookie Policy.