题目描述

有一个弹球游戏，游戏由 n 行 m 列的网格组成，除最后一行的网格外，其余每个网格中都有一个元素（仙人掌、旋风或地洞）。将弹球投向第一行的网格，弹球到达不同的元素网格会有不同的效果：1）到达仙人掌网格：弹球被粘住，无法再移动；

2）到达旋风网格：弹球可被吹向相邻的三个网格之一：左下、正下、右下，若某个方向无相邻网格，则不吹向该方向；

3）到达地洞网格：弹球被向下传送两个网格，若超出网格范围，则传送到地洞正下方相邻的网格。

给定网格的行数 n 和列数 m，以及每个网格中的元素类型，请计算弹球从第一行到达最后一行的网格有多少条路线。

例如：n = 3，m = 3；3 行 3 列的网格如下图所示：

弹球一共有 4 条路线到达最后一行：

输入格式

第一行输入两个整数 $n,m$，表示网格的行数和列数。
接下来输入 $n-1$ 行，每行包含 $m$ 个整数，表示第 $1$ 行到第 $n-1$ 行中每个网格的元素类型：

• 值为 $1$ 表示该网格为“仙人掌”；
• 值为 $2$ 表示该网格为“旋风”；
• 值为 $3$ 表示该网格为“地洞”。

最后一行输入 $m$ 个整数 $0$，表示第 $n$ 行（最后一行）为终点行，不含任何元素。
同一行中相邻整数之间以一个空格分隔。

输出格式

输出一个整数，表示弹球从第一行到达最后一行的不同路线总数。

样例输入输出

样例输入1

3 3
1 2 3
3 1 2
0 0 0

样例输出1

4

数据范围与测试点说明

• $3\le n\le 100$；
• $3\le m\le 100$；
• 前 $n-1$ 行的网格元素类型只可能为 $1,2,3$；
• 第 $n$ 行的网格元素全部为 $0$。

时间限制与内存限制

• 时间限制：$1$ 秒
• 内存限制：$1024$ KiB