Palindromic Paths

Given a square table of size n × n filled with natural numbers, we are interested in finding paths from the top-left corner to the bottom-right corner. These paths can only move right or down, never left or up. Each path will consist of 2n - 1 numbers. If the sequence of numbers along a path reads the same forwards and backwards, we call it a palindromic path.

Task

Your task is to calculate the total number of palindromic paths in the given table.

Input

The input begins with a single integer n (2 ≤ n ≤ 100), representing the size of the table. This is followed by n lines, each containing n natural numbers, none exceeding 10,000, which populate the table.

Output

Output a single number: the remainder when the total number of palindromic paths is divided by 101.

Example

In the first example, there are four palindromic paths:

1. right — right — down — down (7–10–5–10–7);

2. right — down — right — down (7–10–8–10–7);

3. down — right — down — right (7–5–8–5–7);

4. down — down — right — right (7–5–8–5–7).

In the second example, all 252 possible paths are palindromic. Therefore, the output should be the remainder of 252 divided by 101, which is 50.

Examples