Due to the failed experiment in the laboratory of our scientist Digo, a new universe of N dimensions is created with one single virus at origin at time T = 0.

Each point in this new universe can be represented by a linear array of indices (c1, c2, c3 ... cn) where ci represents the i th coordinate. In this new universe we are interested in only integer points i.e, points with integer coordinates. Two points (a1, a2 ... an), (b1, b2 ... bn) are adjacent to each other if sum of abs(ai - bi) for all i is equal to 1 (abs() is the absolute value function). If observed carefully one can observe that there are 2×N adjacent points for every point in the universe. Origin is (0, 0 ... n times).

The virus reproduces very rapidly. After every second it gives birth to 2×N identical new viruses of its kind and dies. As the newly born viruses are born, each of them moves to a distinct point, each of which are adjacent to the point at which the parent was present. New Viruses reproduce at their respective points and this procedure goes on. As the viruses are very small, any number of viruses can stay at a single point.

Now Our Scientist Digo has Q queries. In each query he gives you two integers N and T, and you need to tell him how many viruses are present at the origin in N dimension universe at the end of T seconds.

As the output can be huge print each output modulo (10⁹ + 7).

Input Format

First line contains a single integer Q representing the number of queries.

Q lines follow with two space separated integers N and T in each line. N, T have their respective meanings mentioned in the problem statement.

Output Format

Print a single integer for every query in a separate line.

Constraints

1 ≤ Q ≤ 20000

1 ≤ N ≤ 100

1 ≤ T ≤ 200

Sample

Input:
3
1 2
2 3
3 2

Output:
2
0
6