Elijah is a good "friend" of Miku, and he visits her every day. On the way from Elijah's house to Miku's, there is a mystical forest with lots of mushrooms. Since there are only three edible types of mushroom in the forest, Elijah numbered them 1, 2, and 3 respectively. To please Miku, Elijah decided that every time he comes over, he will pick at least 2 types of edible mushroom for soup.

          The mystical forest is divided into a grid of m rows and n columns. The rows of the grid are numbered from top to bottom starting from 1, and the columns are numbered from left to right, starting from 1. The cell at the intersection of row i and column j has coordinates (i, j). On each cell, except for cells (1, 1) and (m, n), there can be no edible mushroom (marked 0), or one edible one (marked 1 to 3), or a poisonous mushroom and Elijah wants to avoid (marked -1). When Elijah arrives at a cell with an edible mushroom, he will pick it up. The mushrooms will grow back the next day if it were picked up.

          Elijah start from cell (1, 1), and Miku's house is at cell (m, n). The best way for Elijah to travel is to go right or down, which he always does cause Miku's waiting.

          The trip to Miku's house is actually very dangerous because there is an evil kangaroo who always watches and follows Elijah to beat him up. To avoid the roo, Elijah decided that he will use a different route each day. (2 routes are different from each other if there is at least one cell that exists in one but not the other)

Requirement

Given a m x n table describing the forest, calculate the number of routes that Elijah can visit Miku.

Input

-        The first row contains two integer m and n (1 < m, n ≤ 100)

-        Each of the m following rows contains n integers with information about the cells of the forest. The value of cell (1,1) and (m,n) is always 0. The rest of the cells have the value of -1, or 0, or 1, or 2, or 3.

-        Two numbers on the same row is separated by a space.

Output

An integer that is the answer

Subtasks

50% of the test cases have (m,n ≤ 10)

Time limit

1 second

Example

Input:
3 4
0 3 -1 2
3 3  0 3
3 1 3 0

Output:
3