There are $n$ cells arranged in a row, numbered $1, 2, \dots, n$ from left to right. Each cell contains a numbered card; initially, the card in cell $i$ has the number $i$.

A shuffler performs $n$ swap operations to arrange these cards: in each operation, the shuffler chooses two cells $i$ and $j$ ($i \neq j$) and swaps the cards in those cells. After $n$ swap operations, the arrangement of the cards is complete.

Then it is the player's turn. The player also uses swap operations, each swapping two cards, with the goal of restoring the cards to their initial order.

The time required to swap the cards in cell $i$ and cell $j$ is $|i-j|$. The player intends to restore the arrangement in the minimum possible time. How many possible arrangements exist such that the player can complete the restoration in a total time not exceeding $m$? Two arrangements are considered different if and only if at least one numbered card is in a different cell in the two arrangements.

Input

The input is read from standard input.

Each test case consists of multiple data sets.

The first line contains a positive integer $T$, representing the number of data sets. It is guaranteed that $T \le 1,000$.

Each of the following $T$ lines contains two positive integers $n$ and $m$. It is guaranteed that $2 \le n \le 500$ and $m \le 5,000$.

Output

Output to standard output.

For each data set, output a single integer representing the answer.

Since the answer may be very large, output the result modulo $1,000,000,007$.

Examples

Input 1

6
2 1
3 1
5 2
7 5
10 20
15 24

Output 1

1
2
7
331
1570446
73880648

Note

In the first data set, the shuffler's $2$ operations can only be swapping the cards in cell $1$ and cell $2$. There is only $1$ possible arrangement, which is the initial state $[1, 2]$.

In the second data set, there are $2$ possible arrangements: $[1, 3, 2]$ and $[2, 1, 3]$. Note that the initial state $[1, 2, 3]$ is not a possible arrangement, because after the shuffler performs the first $2$ swaps, all cards are either in their initial state (if the first $2$ swaps were of the same pair of cards) or all are not in their initial positions (if the first $2$ swaps were not of the same pair), and it is impossible to return to the initial state after the $3$rd swap.

In the third data set, there are $7$ possible arrangements: $[1, 2, 3, 5, 4]$, $[1, 2, 4, 3, 5]$, $[1, 2, 5, 4, 3]$, $[1, 3, 2, 4, 5]$, $[1, 4, 3, 2, 5]$, $[2, 1, 3, 4, 5]$, and $[3, 2, 1, 4, 5]$.