Palindromic Paths#7826

Palindromic Paths

1 second

64 megabytes

Hard

Given a square table of size $n \times n$ n \times 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 $2 n - 1$ 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 \leq n \leq 100$ 2 \le n \le 100), representing the size of the table. This is followed by $n$ lines, each containing $n$ natural numbers, none exceeding $10000$ , which populate the table.

Output

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

Examples

Example 1

Example 2

Note

In the first example, there are four palindromic paths:

$1)$ right — right — down — down $(7 - 10 - 5 - 10 - 7)$ (7-10-5-10-7);

$2)$ right — down — right — down $(7 - 10 - 8 - 10 - 7)$ (7-10-8-10-7);

$3)$ down — right — down — right $(7 - 5 - 8 - 5 - 7)$ (7-5-8-5-7);

$4)$ down — down — right — right $(7 - 5 - 8 - 5 - 7)$ (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$ .