题目描述
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
输入格式
见题面
输出格式
见题面