Secret Meeting

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:

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:

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.