Naruto went on a search for Tsunade, the 5th Hokage of the Leaf Village. But Tsunade didn't want to meet anyone. The path from Leaf Village to the Tsunade can be represented in the form of a matrix of size \(N\times M\) where N is the number of rows (numbered from 1 to N) and M is the number of columns (numbered from 1 to M). The Leaf Village is located in the row number 1 while Tsunade might be anywhere in the \(N^{th}\) row.

The M cells of the \(1^{st}\) row denote the M exits from the Leaf Village and Naruto can from any such exit. Tsunade has set up a trap in some cells of the matrix (as she does not want anyone to reach her) in such a way that one can only move from a cell in the \(i^{th}\) row, say (i,j) to a cell in the \((i+1)^{th}\) row, say (\(i+1\),k) according to the following conditions, provided this cell (\(i+1\),k) is within the matrix :-

• If \(i \% 3 == 0\), then k can take values \(j-1\), j and \(j+1\).
• If \(i\%3==1\), then k can take values \(j-2\), j and \(j+2\).
• If \(i\%3==2\), then k can take values \(j-3\), j and \(j+3\).

Now Naruto wants to know the number of ways in which he can reach Tsunade, which is the number of ways in which he can reach any cell in the \(N^{th}\) row, starting from any cell (exit from the Leaf Village) in the \(1^{st}\) row.

Input Format
The first line of input contains a single integer T denoting the number of test cases.
Each test case consists of a single line of input consisting of 2 space separated integers N and M denoting the number of rows and number of columns respectively.

Output Format
The output of each test case should be a single integer which is the answer to the problem printed on a new line. As the answer can be very large, print the answer modulo \(10^{9}\)+7.

Constraints

• \(1 \le T \le 50\)
• \(2 \le N \le 10^{9}\)
• \(1 \le M \le 50\)