Background

Even if I myself will be drowned in

endless sorrow,

I will still return to blankness,

to a blank future.

Problem Description

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)$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$.

The next $T$ lines each contain two integers $n, d$.

Output Format

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)$.

3
2 0
10 0
100 0

10
836833797
850061004

3
1000 1
2000 2
4000 45

300382194
871761782
343429692

Hint

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}

Translated by ChatGPT 5