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
| Input | Output |
|---|---|
2 5 2 5 2 | 10 |
| Input | Output |
|---|---|
3 15 5 12 3 12 5 | 526 |
| Input | Output |
|---|---|
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.
