对于一个数 ，我们按如下方式确定一个有 个点的无重边二分图 ：
二分图 是一个可黑白二染色的无向图，其中有 个黑色点与 个白色点。令所有黑色点构成的集合为 ，所有白色点构成的集合为 。
令 表示集合 的编号为 的点， 表示集合 的编号为 的点，其中满足 。 与 有一条无向边，当且仅当下列条件至少有一条成立：
- Timeout waiting for MathJax: restarting
令 Timeout waiting for MathJax: restarting 表示 的本质不同的最大匹配的个数。两个匹配本质不同当且仅当存在 使得其在一种方案中与 匹配，在另一种方案中不与 匹配。
共 组询问，每组询问给出 ，求 。
输出答案对 取模的结果。
