The Academy is a school where each common area is laid out on an grid and each cell in the grid is meter by meter. Danielle is their new head of security, and she wants to place a surveillance camera along every square meter of each common area. Because the school doesn't have enough money in their security budget to do this, she decides to further restrict camera placement according to the following rules:
- Each cell can contain at most camera.
- Every subgrid of a common area must have exactly cameras.
Given the values of and for common areas, determine the number of ways Danielle can install cameras in each common area according to the rules above. Then, for each common area, print the number of ways she can install these cameras on a new line. As these values may be quite large, your answer must be modulo .
Input Format
The first line contains an integer, , denoting the number of common areas to install cameras in.
Each line of the subsequent lines contains two space-separated integers describing the respective values of and for a common area's grid.
Constraints
For of the maximum score:
For of the maximum score:
For of the maximum score:
Output Format
For each common area, print an integer denoting the number of ways Danielle can install the cameras according to the given rules, modulo , on a new line.
Sample Input 0
2
3 3
3 4
Sample Output 0
36
78
Explanation 0
The diagram below depicts the number of ways to place cameras in a grid:
As there are ways to place cameras in this common area, we print the result of on a new line.