A rat started his search of cheese from the (1,1) cell and has to reach (n,n) cell for it. He can move only in the 4 directions i.e. left, right, up or down. The obstructed cells for the rat are marked with 1 and allowed cells are marked with 0 in the maze.

Your task is to find a path through which the rat move from the starting position (1,1) to the final position where cheese is (n,n). List the total no of possible paths which the rat can take to reach the cheese.

Input

First line contains the size of the square maze.

The next n lines contain n binary values separated by space. 0 denotes an open cell while 1 denotes a blocked cell.

You have to find paths which contain only cells which are open, and finally print the total no of such unique paths. Retracing the 1 or more cells back and forth is not considered a new path. The set of all cells covered in a single path should be unique from other paths

Output

The output should be the total no. of paths possible on the first line.

Example

Input: 7 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 1 0 0 0 Output: 4