题目描述

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

（1）到达仙人掌网格：弹球被粘住，无法再移动；

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

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

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

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

输入格式

第一行输入两个整数 n、m（3≤n，m≤100），表示弹球游戏中网格的行数和列数，整数之间以一个空格隔开；
接下来输入 n - 1 行，表示第 1 行到第 n - 1 行的网格情况，每行 m 个整数，整数只能为 1、2、3；1 表示该网格元素是仙人掌、2 表示该网格元素是旋风，3 表示该网格元素是地洞，同一行的整数之间以一个空格隔开；
最后一行输入 m 个 0，0 表示该网格是第 n 行（最后一行）的网格，整数之间以一个空格隔开。

输出格式

输出一个整数，表示弹球从第一行到达最后一行的网格有多少条路线。

样例数据

input

3 3
1 2 3
3 1 2
0 0 0

output

4