Instead of one grid various square grids of odd length came into existence later after the old grid was recovered. Now researchers came to know that for such grids the sum of all the numbers except the middle element is equal to the middle element of the grid. Now since all numbers are disappeared so you need to find total possible solutions the grid can possess. Remember that each element of the grid solution should possess only non negative numbers
Input
First line contains t (test cases) ,next t lines contain N and M as input , N will be odd and is the size of the grid and M is the value of the middle element of the grid
Output
You have to output count of total solutions that the grid can posses mod 10^9+7.
Scoring
1≤ t,N,M ≤ 10 20pts
1≤ t,N,M ≤ 100 30pts
1≤ t ≤ 10^5 , 1≤ N,M ≤ 10^3 50pts

SAMPLE INPUT
1
3 1

SAMPLE OUTPUT
8

Explanation

The all possible solutions to the grid are insert 1 in 8 distinct positions and fill rest with zeros.

见题面

见题面