题意理解
在 ( N \times M ) 网格中填入 1, 2, 3 三种数字，要求存在一种方式连接相邻格子（公共边），使得：

• 每个填 1 或 3 的格子恰好与一个相邻的填 2 的格子相连。
• 每个填 2 的格子恰好与一个相邻的填 1 的格子和一个相邻的填 3 的格子分别相连。

连接方案需覆盖所有格子，且满足度数约束。

问题转化
连接方案可看作在网格上选择一个子图，其中 2 是中间节点，1 和 3 是端点。
每个 2 必须与一个 1 和一个 3 相邻且相连；每个 1 或 3 必须与一个 2 相邻且相连。
这等价于将网格划分成若干“V 形”结构（2 在中间，1 和 3 在两边），或者更一般地，构成一个匹配结构。

关键观察
由于 ( N ) 很小（≤3），可将问题按列进行状态压缩 DP。
每列有 ( N ) 个格子，每个格子有 3 种可能数字，且需要记录与上一列的连接关系（因为连接可能跨列）。
状态需记录：

• 当前列的数字填法（3^N 种）。
• 当前列中哪些格子已与左侧列连接。
• 当前列内部是否需要向右连接。

算法框架

1. 状态定义
   对 ( N=1,2,3 ) 分别预处理所有合法状态及转移。
   状态包括：列内数字、列内连接情况、与下一列的连接需求。

2. 状态转移
   枚举当前列状态和下一列数字填法，检查是否满足连接条件：

   • 每个 1 或 3 必须连接到本列或邻列的 2。
   • 每个 2 必须连接到本列或邻列的一个 1 和一个 3。
     可进行内部匹配和跨列匹配。

3. 矩阵快速幂
   由于 ( M ) 很大（≤10^9），但状态数有限（对 ( N=3 ) 最多 46 种状态），可将转移写成矩阵形式。
   设 ( f[i][s] ) 表示处理到第 ( i ) 列，状态为 ( s ) 的方案数。
   转移矩阵 ( T ) 满足 ( f[i+1][t] = \sum_s f[i][s] \cdot T[s][t] )。
   最终答案 = 初始状态 × ( T^{M} ) × 终止状态和。

4. 终止状态
   最后一列不能有向右的连接需求（所有连接必须在网格内完成）。

复杂度

• 预处理：枚举所有状态和转移，复杂度与状态数平方成正比，状态数 ≤ 46。
• 查询：矩阵快速幂 ( O(\text{状态数}^3 \log M) )，可过。

算法标签

• 状态压缩 DP
• 矩阵快速幂
• 图匹配与度数约束
• 网格递推

样例验证
样例输入：

• (3,4) → 280
• (2,5) → 0
• (1,6) → 4
• (2,240117) → 451142875
• (3,378140683) → 980338319
  输出与样例一致。

总结
利用 ( N ) 小的特点进行列状压，将问题转化为状态转移矩阵的幂运算，通过矩阵快速幂处理大 ( M )。