#2550. 「JSOI2018」机器人

内存限制:256 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

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

九条可怜的家可以抽象成一个 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 取模后输出。

样例

样例输入 1

2
2 4
0111
1111
2 4
0010
1000

样例输出 1

2
5

样例说明 1

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

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

样例 2

见下发文件。

数据范围与提示

测试数据 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