A maze can also be considered as a Graph. Given a maze A of size n x n with cells containing binary values. Find the number of ways to reach from cell (0, 0) to (n-1, n-1). If A[i][j] = 1 then it is possible to visit cell A[i][j] else not. From a cell (i, j) only two kind of movement is possible (i+1, j) or (i, j+1).

Input Format:

First line of input file contains an integer n denoting the size of maze. Followed by n lines, each line contains n space separated integers with value 0 or 1 only.

Output Format:

For each input print a single integer denoting number of ways to reach from cell (0, 0) to (n-1, n-1).

Constraints:

1 <= n <= 12

0 <= A[i][j] <= 1