Problem Description

Alice and Bob are going to Tenbaba for an interview. There are totally N candidates(including Alice and Bob) applying for this job. The recruitment process of Tenbaba is strict. So all of them need to have an interview with the department manager. N candidates will get a unique integer from $1$ to $N$ with equal probability. And they will go to interview with the manager according to the number they get. The candidate with number 1 will be interviewed firstly, the candidate with number 2 will be interviewed secondly and so on.

What's more, HR(the staff to arrange the interview for you) will randomly choose a nonnegative integer $K$ in range $[0..N]$ with equal probability. The candidates whose numbers are not greater than $K$ will be interviewed in order of their numbers on the first day. Remaining candidates will be interviewed in order of their numbers on the second day. Candidates don't know $K$. But each one will knows on which day he or she will be interviewed.

Sadly, Alice forgot her number. The only thing she remember is that she will be interviewed on the second day. Alice also knows on which day Bob will be interviewed. But she doesn't know the exact number Bob has. Assume that Alice would be the $Y$-th$(1\leq Y \leq N - K)$ candidate to interview with the manager on the second day. Please help Alice to calculate the expectation of $Y$ because Alice doesn't want to go out too early.

Input

The first line is the number of test cases. It's guaranteed that the test cases is not greater than $10^5$.

Each test case contains two integers $N$ and $D$ $(2 \leq N \leq 10^9, D = \ 1 \ or \ 2$). $D = 1$ means Bob will be interviewed on the first day and $D = 2$ means Bob will be interviewed on the second day.

Output

Each test case contains one line with one integer. Let¡ˉs assume the possibility be equal to the irreducible fraction $P / Q$. Print the value of $P\cdot Q^{-1}$ in the prime field of integers modulo $1000000007(10^9+7)$.

3
2 1
3 2
100 1

1
875000008
500000029