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
Hint
there are 1 solutions is"ABCDCBA" there are 1 solutions is"ABCGCBA" there are 4 solutions is"ABEDEBA" there are 6 solutions is"ABEFEBA"

Hint

hujie

Source

BestCoder Round #70

提交代码