#P17731. [2026年福建省队集训]鼓手

[2026年福建省队集训]鼓手

题目描述

小 A 是乐队的鼓手。小 A 的鼓是一个圆柱体,在鼓面上包裹了一张矩形网格。

小 A 的乐队即将在数字岛演出。数字岛的观众非常挑剔,他们要求小 A 的鼓面上的每个格子都填上正整数,不能有零或负数。此外,每个整数 KK 必须恰好与 KK 个相同整数的格子相邻(即共享一条边,而不仅仅是一个点)。也就是说,一个填了 11 的格子,必须恰好与一个填了 11 的格子相邻;一个填了 22 的格子,必须恰好与两个填了 22 的格子相邻,依此类推。除此之外,格子与其它格子的接触情况没有限制。(鼓的顶部和底部不是格子,不需要装饰。注意,这意味着鼓面最上面和最下面一行的格子每个只与三个格子相邻,而其它格子每个与四个格子相邻。)

例如,下图是一个 33 行 55 列的圆柱鼓面的一种合法装饰方式(自行想象将其环绕成一个圆柱):

$$\begin{matrix} 3&3&3&3&3\\ 3&3&3&3&3\\ 2&2&2&2&2 \end{matrix}$$

小 A 想知道有多少种不同的合法装饰方案。如果两个装饰无法通过绕圆柱轴旋转得到彼此,则认为它们是不同的。鼓的顶部和底部视为不同,因此下图的 3×53\times 5 鼓面装饰与上图不同:

$$\begin{matrix} 2&2&2&2&2\\ 3&3&3&3&3\\ 3&3&3&3&3 \end{matrix}$$

小 A 的鼓有 nn 行和 mm 列。请问有多少种不同的合法装饰方案?答案可能很大,请输出方案数对 109+710^9+7(10000000071000000007)取模后的结果。

输入格式

本题有多组测试数据。

第一行 11 个整数 TT,表示测试数据组数。

接下来依次输入每组测试数据,对于每组测试数据,输入一行 22 个整数 n,mn,m,表示鼓有 nn 行和 mm 列。

输出格式

对于每组数据,输出一行一个整数,表示合法装饰方案数对 109+710^9+7 取模后的结果。

样例

样例输入 1

5
2 4
3 5
4 6
7 18
10 24

样例输出 1

1
2
5
9
182

样例解释 1

对于第 11 组数据,唯一的方案是所有格子都填 33。

对于第 22 组数据,只有题目描述中给出的两种方案。

样例 2

见选手目录下的 drum/drum2.in 与 drum/drum2.ans。

这个样例满足测试点 4∼54\sim 5 的约束条件。

样例 3

见选手目录下的 drum/drum3.in 与 drum/drum3.ans。

这个样例满足测试点 6∼76\sim 7 的约束条件。

样例 4

见选手目录下的 drum/drum4.in 与 drum/drum4.ans。

这个样例满足测试点 8∼108\sim 10 的约束条件。

数据范围

对于 100%100\% 的数据,1≤T≤1001\le T \le 100,2≤n≤1092\le n\le 10^9,3≤m≤1093\le m\le 10^9。

测试点编号 nn mm
11 ≤6\le 6 1$
2∼32\sim 3 ≤100\le 100
4∼54\sim 5 ≤105\le 10^5 ≤105\le 10^5
6∼76\sim 7 ≤109\le 10^9
8∼108\sim 10 ≤109\le 10^9