Problem Statement

There is a grid of $N×N$ cells. Each cell $(i,j)\space (1 \leq i,j \leq N)$ has a lowercase English letter $c_{i,j}$ written on it.
Starting from the top-left cell $(1,1)$, you move to the goal at the bottom-right cell $(N,N)$ by repeatedly moving only right or down.
Let $S$ be the string obtained by reading, in order, the characters written on the $2N-1$ cells passed through (including the start and the goal).
Among the paths from cell $(1,1)$ to $(N,N)$, how many are there for which the string $S$ is a palindrome?
Here, a string $T$ of length $M$ is a palindrome if, for every $1 \leq i \leq M$, the $i$-th character and the $(M+1-i)$-th character of $T$ are equal.
Since the answer can be very large, output it modulo $998244353$.

Input

• $2 \leq N \leq 10$
• $c_{i,j}$ is a lowercase English letter

$N$
$c_{1,1}c_{1,2}...c_{1,N}$
$c_{2,1}c_{2,2}...c_{2,N}$
$\vdots$
$c_{N,1}c_{N,2}...c_{N,N}$

Output

Output the total number of paths that form a palindrome, modulo $998244353$.

Sample

3
aba
aba
aba

2

3
ynu
cpc
con

0

10
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa

48620