[JSOI2018]机器人

题目描述

九条可怜是一个懒懒的女孩子。因为懒得扫地,九条可怜买了一架扫地机器人。 九条可怜的家可以抽象成一个 $n \times m$ 的网格,坐标从 $(1,1)$ 到 $(n,m)$ 。每一天晚上,可怜都会在 $(1,1)$ 处启动扫地机器人。在启动了之后,扫地机器人会按照设定好的路径开始行动,当再一次回到 $(1,1)$ 后便会停止。 因为一些技术原因,扫地机器人只能向右(列编号加一)或者向下(行编号加一)走。为了让扫地机器人能够顺利的回到 $(1,1)$ ,可怜在家中安装了一些通道,使得: 1. 如果机器人目前在 $(i,m)$ ,那么向右走一步会到 $(i,1)$ 。 2. 如果机器人目前在 $(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$ 取模后输出。

输入输出样例

输入样例 #1

2
2 4
0111
1111
2 4
0010
1000

输出样例 #1

2
5

说明

**样例 1 解释** $n=2,m=4$ 时,一共有两种合法的方案: ![0](https://i.loli.net/2018/05/05/5aed14bde4548.png) 在第一种方案中,机器人在撞上障碍 $(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$ 。