背景

就算自身将浸于

无边无际的悲叹

也要回归空白

空白的未来

题目描述

对于一个长度为 $2n$ 的排列 $p$，定义 $f(p)$ 为满足以下条件的整数数对 $(i,j)$ 的个数：

• $1\le i,j\le n$。
• $p_{2i}=2j$。
• $p_{2i-1}=2j-1$。

定义 $c(p)$ 为排列 $p$ 的置换环个数。

对于 $i=0\sim n$，$j=1\sim 2n$，请你求出满足 $f(p)=i$ 且 $c(p)=j$ 的排列 $p$ 的个数对 $10^9+7$ 取模的结果，记为 $H(i,j)$。

请你求出 $\displaystyle \bigoplus_{i=0}^n\bigoplus_{j=1}^{2n} \left(d+H(i,j)\right)$。

输入格式

本题含有多组测试。

第一行，包含一个整数 $T$。

接下来共 $T$ 行，每行包含两个整数 $n,d$。

输出格式

共 $T$ 行，对于每组测试，请你输出一行一个整数，表示 $\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

提示

对于所有数据，保证 $1\le T\le 3$，$1\le n\le 4000$，$0\le d\le 100$。

::cute-table{tuack}