题目描述

As you may already know, Eddy likes to walk around. Especially, he likes to walk in a number line called "Infinite line". Actually, it's exactly a line with infinite length!

Eddy is at number 0 and starts to walk around. Since Eddy is a little drunk(just finished his work, make sense), he will not walk in a fixed length. Instead, he will independently uniformly randomly walk in an integer length between 1 and K. That is, he will walk for 1 unit of length in a probability of $\frac{1}{K}​$, 2 units in $\frac{1}{K}$​, ⋯⋯, K units in $\frac{1}{K}$​. If he currently stands on number i and walk for j unit of length, he will end up on number i+j.

Since Eddy is drunk, he will walk around infinitely. You, somehow, notice this weird thing and start wondering whether will Eddy ever step on the number N. However, you don't want to wait for such stupid thing. You would like to compute the probability that Eddy would ever step on number N.

输入格式

The first line of input contains an integers T. Following T lines each contains two space-separated integers $K_i$ and $N_i$​. If $N_i = -1$, $N_i$​ is a number approaching infinity.

输出格式

For each i, output one line containing a number representing the probability. you should output the number module $109+7(1000000007).$ Suppose the probability is $\frac{P}{Q}$, the desired output will be $mod 10^9+7$

样例

样例输入 1

3
1 0
2 1
3 -1

样例输出 1

1
500000004
500000004

数据范围与提示

1≤T≤10

$1≤Ki​≤1021$

$\textbf{-1} \leq N_i \leq 10^{18}$