#P17731. [2026年福建省队集训]鼓手
[2026年福建省队集训]鼓手
题目描述
小 A 是乐队的鼓手。小 A 的鼓是一个圆柱体,在鼓面上包裹了一张矩形网格。
小 A 的乐队即将在数字岛演出。数字岛的观众非常挑剔,他们要求小 A 的鼓面上的每个格子都填上正整数,不能有零或负数。此外,每个整数 必须恰好与 个相同整数的格子相邻(即共享一条边,而不仅仅是一个点)。也就是说,一个填了 的格子,必须恰好与一个填了 的格子相邻;一个填了 的格子,必须恰好与两个填了 的格子相邻,依此类推。除此之外,格子与其它格子的接触情况没有限制。(鼓的顶部和底部不是格子,不需要装饰。注意,这意味着鼓面最上面和最下面一行的格子每个只与三个格子相邻,而其它格子每个与四个格子相邻。)
例如,下图是一个 行 列的圆柱鼓面的一种合法装饰方式(自行想象将其环绕成一个圆柱):
$$\begin{matrix} 3&3&3&3&3\\ 3&3&3&3&3\\ 2&2&2&2&2 \end{matrix}$$小 A 想知道有多少种不同的合法装饰方案。如果两个装饰无法通过绕圆柱轴旋转得到彼此,则认为它们是不同的。鼓的顶部和底部视为不同,因此下图的 鼓面装饰与上图不同:
$$\begin{matrix} 2&2&2&2&2\\ 3&3&3&3&3\\ 3&3&3&3&3 \end{matrix}$$小 A 的鼓有 行和 列。请问有多少种不同的合法装饰方案?答案可能很大,请输出方案数对 ()取模后的结果。
输入格式
本题有多组测试数据。
第一行 个整数 ,表示测试数据组数。
接下来依次输入每组测试数据,对于每组测试数据,输入一行 个整数 ,表示鼓有 行和 列。
输出格式
对于每组数据,输出一行一个整数,表示合法装饰方案数对 取模后的结果。
样例
样例输入 1
5
2 4
3 5
4 6
7 18
10 24
样例输出 1
1
2
5
9
182
样例解释 1
对于第 组数据,唯一的方案是所有格子都填 。
对于第 组数据,只有题目描述中给出的两种方案。
样例 2
见选手目录下的 drum/drum2.in 与 drum/drum2.ans。
这个样例满足测试点 的约束条件。
样例 3
见选手目录下的 drum/drum3.in 与 drum/drum3.ans。
这个样例满足测试点 的约束条件。
样例 4
见选手目录下的 drum/drum4.in 与 drum/drum4.ans。
这个样例满足测试点 的约束条件。
数据范围
对于 的数据,,,。
| 测试点编号 | ||
|---|---|---|
| 1$ | ||