Go Home

题目描述

小明在学校里上学，放学就要回家。

但回家的路危机重重，在一个 $H\times W$ 的地图上行走，上面有一些怪物，小明得绕开走，但如果挨着怪物，同样会被吃掉，请问他到家一共有几种走法。注意：可能有两个家。

• 1：家
• 2：学校
• 3：墙
• 4：怪物
• 5：路

输入格式

第一行 $H,W$。

接下来是一个 $H\times W$ 的矩阵。

输出格式

输出方案数。

样例

样例 #1输入

5 5
25555
53535
55455
53535
55551

样例 #1输出

2

数据约定

对于 $100\%$ 的数据保证：$10\leqslant H,W\leqslant20$。

方案数可能很大，所以请将答案 $\bmod \quad 99443128$。