P10547 [THUPC 2024 Finals] Permutation Game

An extra 1-second time limit is provided.

There are $n$ cells arranged in a row, numbered from left to right as $1,2,\cdots,n$. Each cell has a number card. Initially, the number on the card in cell $i$ is $i$. The shuffler will perform $n$ swap operations to permute these cards: each time, they choose two cells $i,j$ ($i\ne j$), and then swap the cards in cell $i$ and cell $j$. After the $n$ swap operations, the permutation of the cards is completed. Then it is the player's turn. The player also uses swap operations, swapping two cards each time, with the goal of restoring the order of these cards to the initial state. The time needed to swap the cards in cell $i$ and cell $j$ is $|i-j|$. The player plans to restore the permutation in the shortest total time. Ask: how many possible permutations are there such that the player can complete the restoration with a total time of at most $m$? Two permutations are different if and only if there exists at least one number card whose cell position differs between the two permutations.

Each test point consists of multiple test cases. The first line contains a positive integer $T$, indicating the number of test cases. It is guaranteed that $T\le1,000$. Then follow $T$ lines. Each line contains one test case with two positive integers $n$ and $m$. It is guaranteed that $2\le n\le500$ and $m\le5,000$.

For each test case, output one line with one integer representing the answer. Since the answer may be very large, output the result modulo $1,000,000,007$.

In the first test case, the shuffler's $2$ operations can only be swapping the cards in cell $1$ and cell $2$, so there is only $1$ possible permutation, namely the initial state $[1,2]$. In the second test case, there are $2$ possible permutations: $[1,3,2]$ and $[2,1,3]$. Note that the initial state $[1,2,3]$ is not a possible permutation, because after the shuffler performs the first $2$ swaps, either all cards are still in the initial state (the first $2$ swaps are on the same pair of cards), or none of the cards are in their initial positions (the first $2$ swaps are not on the same pair of cards). After the third swap, it is impossible to return to the initial state. In the third test case, there are $7$ possible permutations: $[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]$, $[3,2,1,4,5]$. **Source and Acknowledgements** From the THUPC2024 Finals (Tsinghua University Student Programming Contest and Intercollegiate Invitational, 2024). Thanks to THUSAA for providing the problem. For the testdata, statement, reference solution, editorial, etc., please refer to the THUPC official repository . Translated by ChatGPT 5