Puzzle: Grid Traversal

Traverse through the board

Problem code: TRAVERSE
---------------------------------

An n x n game board is filled with integers, one positive integer per square. The objective is to travel along any legitimate path from the upper left corner to the lower right corner of the board.

Rules

1.The number in any one square describes how far a step away from that location must be.
2.If the step size moves out of the game board, then that step is not allowed.
3.All steps must be either to the right or towards the bottom.

Note that a 0 is a dead end which prevents any further progress.

Consider the 4 x 4 board shown in Figure 1, where the solid circle identifies the start position and the dashed circle identifies the target. Figure 2 shows the three paths from the start to the target, with the irrelevant numbers in each removed.

http://lulzimg.com/view/0bac00.jpg

Input

The first line contains the value of n followed by a nxn matrix depicting the board configuration.

Output

The output consists of  a single integer, which is the number of paths from the upper left corner to the lower right corner.

Example

Input:

4
2331
1213
1231
3110

Output:
3

Input:

4
3332
1213
1232
2120

Output:

0

Input:

5
11101
01111
11111
11101
11101

Output:
7

<<Solution done. Contact steve_robinson@live.com>> footyntech.wordpress.com