# Jam's maze

Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

## Description

Jam got into a maze, he has to find a palindrome path from $(1,1)$ to $(N,N)$ to get out.
However he is not only thinking about how to get out of the maze,
but also counting the number of ways he can get out.

The maze a $N*N$ grid. On each cell is a uppercase letter.
Jam is at upper-left corner $(1,1)$ now, and the exit is at lower-right corner $(N,N)$.
Jam can only go down or go right.
Considering the number of palindrome path may be huge, you just need to output the number mod $5201314$.

## Input

The first line is $T(1 \leq T \leq 10)$ means $T$ Case.
For each case:
The first line is $N(1 \leq N \leq 500)$ means the size of the maze.
Then $N$ lines follow, each line has $N$ uppercase letter.

## Output

For each testcase, output the number of palindrome path mod $5201314$.

## Sample Input

1
4
ABCD
BEFE
CDEB
GCBA

## Sample Output

12

Hintthere are 1 solutions is"ABCDCBA"
there are 1 solutions is"ABCGCBA"
there are 4 solutions is"ABEDEBA"
there are 6 solutions is"ABEFEBA" 

hujie

## Source

BestCoder Round #70