Tyrion Lannister!!

Limits 2s, 512 MB

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-

He will drink exactly K liter(s) of wine.
Sometimes he can drink K liters of wine of same type, sometime he can mix different types of wine to drink.
He will keep record of the variations. Also he does not want to drink same type of variation again. You can assume that mixture of one, two and three is different variation from mixture of one, two and four. But three, two and one is as same as one, two and three.

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.

Input

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

Output the desired result.

Sample

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).