dummy-4-1

Given a square binary grid, you are to find the number of ways to reach the bottom-right corner from the top-left corner of the grid. The rules for the same are follows:
You can travel only on grid positions marked by '0'.
You can travel in horizontal or vertical directions only.
You are not allowed to travel a grid position more than once during one path. 

Input:
First line is an integer N ( N ≤ 100), which is the size of the grid. N lines follow, each containing N space separated numbers which are either '0' or '1'.

Output:
Print a single line which is the answer to the given puzzle.

SAMPLE INPUT
9
0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0

SAMPLE OUTPUT
8512

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: