Torus Loop

时间限制：2s
空间限制：1024MB

题目描述

有一个 $H$ 行 $W$ 列的网格，行、列均从 $0$ 开始编号。每个格子放置一种可以自由旋转的线段砖块，砖块类型由仅含 A、B 的字符串 $S_0,S_1,\ldots,S_{H-1}$ 指定：

• A 型砖块上的线段连接两个相邻边的中点，共有 $4$ 种旋转方式；
• B 型砖块上的线段连接两个相对边的中点，共有 $2$ 种旋转方式。

把网格的上下边、左右边分别首尾相接成环面。要求相邻格子公共边的中点要么同时是两块砖上线段的端点，要么同时都不是，从而所有线段均没有断头。求满足条件的砖块旋转方案数对 $998244353$ 取模的结果。共有 $T$ 组测试数据。

输入格式

T
H_1 W_1
S_{1,0}
\vdots
S_{1,H_1-1}
\vdots
H_T W_T
S_{T,0}
\vdots
S_{T,H_T-1}

输出格式

输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

样例输入 1

3
3 3
AAB
AAB
BBB
3 3
BBA
ABA
AAB
3 4
BAAB
BABA
BBAA

样例输出 1

2
0
2

数据范围

$1\le T\le 10^5$，$2\le H,W$，单组 $HW\le 10^6$，所有测试数据的 $HW$ 之和不超过 $10^6$。