P17341 [MX-X30-T7] Redemption of the Untrustworthy

> Even if I myself will be drowned in > > endless sorrow, > > I will still return to blankness, > > to a blank future.

For a permutation $p$ of length $2n$, define $f(p)$ as the number of integer pairs $(i, j)$ that satisfy the following conditions: + $1 \le i, j \le n$. + $p_{2i} = 2j$. + $p_{2i-1} = 2j-1$. Define $c(p)$ as the number of permutation cycles of $p$. For $i = 0 \sim n$ and $j = 1 \sim 2n$, please compute the number of permutations $p$ such that $f(p) = i$ and $c(p) = j$, taken modulo $10^9 + 7$, denoted as $H(i, j)$. Please compute $\displaystyle \bigoplus_{i=0}^n \bigoplus_{j=1}^{2n} \left(d + H(i, j)\right)$.

This problem contains multiple test cases. The first line contains an integer $T$. The next $T$ lines each contain two integers $n, d$.

Output $T$ lines in total. For each test case, output one integer per line, representing $\displaystyle \bigoplus_{i=0}^n \bigoplus_{j=1}^{2n} \left(d + H(i, j)\right)$.

For all data, it is guaranteed that $1 \le T \le 3$, $1 \le n \le 4000$, and $0 \le d \le 100$. ::cute-table{tuack} | Subtask ID | Score | $n \le$ | |:-:|:-:|:-:| | $1$ | $5$ | $5$ | | $2$ | $10$ | $15$ | | $3$ | $15$ | $50$ | | $4$ | $20$ | $250$ | | $5$ | $20$ | $2000$ | | $6$ | $20$ | $3000$ | | $7$ | $10$ | $4000$ | Translated by ChatGPT 5