Do you know him?
OK, Can you tell me how long will I have to wait for Season-8 of the famous TV series "Game of Thrones"? Last episode of Season-7 left me thirsty :( .
Anyway, if you are a fan of GOT like me, then you must know the little man named Tyrion Lannister.
I like this cool man from the very beginning of the series. Did you ever notice how tactfully he talks? This really amuses me. None of your business though -_- !
Tyrion is very much fond of drinking wine. He can't even sleep without it.
Drinking wine gives him strength to work and talk much obviously ;) He thinks the more he drinks wine, the more he becomes strong.
He has N different types of wine. Each type has unlimited quantity of it and different strength value.
But he is only allowed to drink some non-negative integer number of liter**(s)** from any type he wants.
Let’s say, 1 liter, 2 liters, 3 liters and so on. He can also drink no wine **(0 liter)** from any type.
Drinking 1 liter of wine of any type will increase his strength by the strength value of that type.
Today Tyrion prepared a daily drinking plan. The rules of the plan are-
Now you have to determine how long he can drink wine without violating the rules of daily drinking plan?
The answer can be very large, so compute it modulo 1000000007 = 10^9 + 7.
Fist line contain T. T denote test cases. Next T line contains two space separated integer N and K. N and K is specified above.
Constraints:
1<=T<=10^5
1<=N<=10^5
0<=K<=10^5
Output the desired result.
Input | Output |
---|---|
2 1 1 2 2 | 1 3 |
Explanation:
Consider the second case. All the possible variation without violating the rules are(red wine, white wine), (red wine, red wine) and (white wine, white wine).