Jump

An N × N game board contains one number in each cell. Starting from the top-left cell, your goal is to reach the bottom-right cell by following the jump rules.

The number written in the current cell is the exact distance you must move from that cell. You may move only to the right or downward. A 0 means the path cannot continue from that cell. Each jump must use exactly the number in the current cell, and its direction cannot change during the jump. In other words, from one cell there are at most two possible jumps: one to the right and one downward.

Write a program that counts how many valid paths lead from the top-left cell to the bottom-right cell.

The first line contains the board size N (4 ≤ N ≤ 100).

Each of the next N lines contains N integers, the numbers written in the board cells. Every cell value is an integer from 0 to 9, inclusive. The bottom-right cell is always 0.

Print the number of valid paths from the top-left cell to the bottom-right cell. The number of paths is at most 2^63 - 1.