P15856 [蓝桥杯第二届国际赛] 游览

蓝桥杯官方提供的题面本题样例有误。根据正确的理解重新计算了样例。

小 E 去一个城市玩，发现这里的道路都是东西向（称为大街，Street）或南北向的（称为大道，Avenue），将街区分成了很多个方块。 城市中一共有 $n$ 条大街，从南向北依次编号 $1$ 至 $n$，有 $m$ 条大道，从东向西依次编号 $1$ 至 $m$。这些大街和大道将城市分区了很多块区域，每一块都相与两条大街和两条大道相邻。有的区域是一个整块，行人无法进入。有的区域被分成了 $2 \times 2$ 的小块，行人可以从正中间的道路通过。下图中给出了一个 $3$ 条大街和 $4$ 条大道的例子，一共有 $6$ 块区域。 :::align{center}  ::: 小 E 现在正站在第 $1$ 大街第 $1$ 大道，他打算游览这个城市，他的计划是走到第 $n$ 大街第 $m$ 大道，然后再走回来。小 E 不想绕路，也不想走重复的路，所以他希望去和回都是走的最短路径，并且路径中不会经过同一段路两次。 有很多种方案都能满足小 E 的要求，请告诉小 E 一共有多少种方案。

输入的第一行包含两个整数 $n, m$，分别表示大街数量和大道数量。 接下来 $n-1$ 行，每行包含 $m-1$ 个整数，表示每块区域的信息，如果对应的整数是 $0$，表示一个行人无法进入的整块区域，如果对应的整数是 $1$，表示一个分成 $2 \times 2$ 小块的区域。为了方便与地图对应，输入的从上到下对应地图的从北到南，输入的从左到右对应地图的从西到东。 因此，从输入来看，小 E 现在站在右下角，他要走到左上角再走回右下角。

输出一个整数，表示总共有多少种方案。如果方案太多，请输出方案数除以 $1000$ 的余数。

### 【样例说明】 对应着问题描述中的例子。注意原题样例输出是 $18$，这应当是错误的，只统计了单程最短路条数。 ### 【数据规模与约定】 对于 $20\%$ 的评测用例，$1 \le n, m \le 5$。 对于 $40\%$ 的评测用例，$1 \le n, m \le 20$。 对于 $60\%$ 的评测用例，$1 \le n, m \le 100$。 对于 $100\%$ 的评测用例，$1 \le n, m \le 1000$。