B. Royale Bataille
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output
Se battre pour la famille royale!

在公元四世纪的欧洲有两个帝国，一个在西北方向，另一个在东南方向，两个部落之间被一条河流隔开。这片土地是一个网格图，每片土地只能被任意一个帝国占有或者是河流。具体而言，使用数字 $$$1$$$ 代表被第一个帝国占有的土地，使用数字 $$$2$$$ 代表被第二个帝国占有的土地，数字 $$$0$$$ 代表河流，河流不属于任何一个帝国的土地。这片土地被使用的规则如下：

  • 两个帝国的土地必须被河流完全隔开，即两片帝国的土地不能有公共边或者公共点（这很严重，不然会引发战争）。
  • 任意一片第一个帝国的土地的西方（地图左侧）和北方（地图上侧）的土地只能是第一个帝国的土地。
  • 任意一片第二个帝国的土地的东方（地图右侧）和南方（地图下侧）的土地只能是第二个帝国的土地。
  • 任意一片是河流的土地的的西方（地图左侧）和北方（地图上侧）的土地只能是河流或者是第一个帝国的土地，东方（地图右侧）和南方（地图下侧）的土地只能是河流或者是第二个帝国的土地。
合法的土地使用方案
不合法的土地使用方案

给你一张只由数字 $$$0,1,2$$$ 和 '?' 组成的地图，'?' 代表不知道当前这片土地是什么，请你求出有多少种使用数字 $$$0,1,2$$$ 填充所有 '?' 的方法，满足这篇土地的使用规则。因为方案数可能很多，请在输出方案数量时对于 $$$998244353$$$ 取模。

Input

第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。

对于每组数据：

第一行，两个整数 $$$n,m(1\le n,m\le 4\cdot 10^4)$$$，分别代表地图的长和宽。

接下来连续的 $$$n$$$ 行，每行一个长度为 $$$m$$$ 的字符串，字符串的每个字符 $$$c\in\{0,1,2,?\}$$$，代表当前的地图。

保证同一测试点内的 $$$\bf{n\times m}$$$ 的总和不超过 $$$4\cdot 10^4$$$。

Output

对于每组数据，输出一行数字，代表合法填充当前地图中所有的 '?' 的方案数，将结果对于 $$$998244353$$$ 取模。

Example
Input
6
1 1
?
1 2
1?
3 3
11?
???
?22
8 10
1111110002
1111000002
111?????22
111???????
11???????2
??????????
????0?2222
0000222222
3 4
1102
1102
0022
2 2
??
??
Output
3
2
4
3100
0
11