Tom and Jerry are wonderful characters. They are always running and make us laugh.

Right now, they are in a grid of houses and Jerry is running away from Tom. The grid of houses is represented as 0 and 1, where 0 means that Jerry can enter the house, and 1 means Jerry can't. Jerry can only move horizontally or vertically. Also, Jerry doesn't enter the same house more than once.

Jerry started running from the house at (1,1) which is the top-left house in the grid and have to reach (N,N) which the bottom-right house in the grid. You have find the number of ways in which Jerry can reach the destination house where he can be safe.

Input Format

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 format

Print a single line showing the number of ways in which Jerry can reach from (1,1) to (N,N).

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

见题面

见题面