2550 「JSOI2018」机器人

九条可怜是一个懒懒的女孩子。因为懒得扫地，九条可怜买了一架扫地机器人。

九条可怜的家可以抽象成一个 $n \times m$ 的网格，坐标从 $(1,1)$ 到 $(n,m)$ 。每一天晚上，可怜都会在 $(1,1)$ 处启动扫地机器人。在启动了之后，扫地机器人会按照设定好的路径开始行动，当再一次回到 $(1,1)$ 后便会停止。

因为一些技术原因，扫地机器人只能向右（列编号加一）或者向下（行编号加一）走。为了让扫地机器人能够顺利的回到 $(1,1)$ ，可怜在家中安装了一些通道，使得：

• 如果机器人目前在 $(i,m)$ ，那么向右走一步会到 $(i,1)$ 。
• 如果机器人目前在 $(n,i)$ ，那么向下走一步回到 $(1,i)$ 。

可怜希望，在启动了机器人之后，在机器人回到 $(1,1)$ 前，它可以经过每一个格子恰好一次。这样既可以把家里给打扫干净，也不会花太多时间。经过简单的计算，可怜很快就得到了所有不同的方案（两个方案是不同的当且仅当他们经过格子的顺序不同）。于是可怜把所有的方案都输入到了扫地机器人里。

这一天可怜购置了一些新的家具，放好家具之后，家里便多了一些扫地机器人无法通过的障碍，于是在所有之前准备的方案中，扫地机器人都会撞上某一个障碍而停止工作。

对于一个方案 $S$，可怜定义 $f(S)$ 为在这个方案中，扫地机器人在撞上障碍之前，经过了多少个格子。现在可怜想要对所有不同的方案，计算 $f(S)$ 的和。

输入包含多组测试数据。输入第一行一个整数 $T$ 表示测试数据的数量。

对于每组测试数据，第一行输入两个整数 $n,m$ ，表示可怜家的大小。

接下来 $n$ 行每行一个长度为 $m$ 的 01 字符串。第 $i$ 行第 $j$ 个字符是 $0$ 表示坐标 $(i,j)$ 的格子不是障碍，否则表示是障碍。

输入保证 $(1,1)$ 不是障碍且至少有一个障碍。

对于每组测试数据，输出一行一个整数表示答案，答案可能很大，对 $998244353$ 取模后输出。

$n=2,m=4$ 时，一共两种合法的方案：

在第一种方案中,机器人在撞上障碍 $(1,3)$ 之前，一共经过了 $4$ 个格子。 在第二种方案中,机器人在撞上障碍 $(2,1)$ 之前，一共经过了 $1$ 个格子。 因此第二组测试数据的答案为 $1 + 4 = 5$ 。

见下发文件。

测试数据 1 ( $20\%$ )：$n,m\le 4$ 。
测试数据 2 ( $30\%$ )：$n,m\le 50$ ，且除了$(1,1)$外所有格子都是障碍。
测试数据 3 ( $50\%$ )：$n,m\le 50$ 。
对于所有测试数据， $T\le 10;n,m\ge 1$。