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.
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 just a single line containing the required value modulo 103003811.
2 5 2 5 2
3 15 5 12 3 12 5
1 50 7
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.