Suppose we have an n-dimensional supercomputer with an infinite number of processors. Every processor has a vector of $n$ integers as its (n-dimensional) coordinates and can be thought of as a point in the $n$-dimensional space. Furthermore, at every $n$-dimensional lattice point, there is a processor. Two processors are called neighbors if their coordinate vectors are different in only one position, and the absolute difference of the numbers in that position is equal to ${1}$. For example $(0,0,0)$ and $(1,0,0)$ are neighbors, and so are $(-1,2,3,4)$ and $(-1,2,3,3)$. But $(0,0,0)$ and $(1,0,1)$, and $(1,2,3,4)$ and $(1,2,3,2)$, are not neighbors.

Some processors of this computer are infected by a virus. At time ${0}$, only one processor is infected. After every second, all uninfected processors that are neighbors with infected ones become infected too. Given $n$ and ${t}}$, calculate the number of processors that are infected after ${t}$ seconds, modulo $(10^9+7)$.

Input Format

The first line contains an integer ${Q}$, the number of test cases.

Each of the next ${Q}$ lines contains two integers $n$ and $\boldsymbol{\boldsymbol{t}}$, separated by a space.

Output Format

For every test case, write the answer in a single line.

Constraints

$1\leq Q\leq10^5$

$1\leq n\leq5\times10^6$

$0\leq t\leq10^{18}$

The sum of all $n$'s in one file does not exceed $5\times10^{6}$

Sample Input
5
2 0
2 1
2 2
3 1
1 10

Sample Output
1
5
13
7
21

Explanation

见题面

见题面