No.1916 Making Palindrome on Gird
とりゐ
箱星
rianoProblem Statement
There is a grid with $H$ rows and $W$ columns. The cell $(i,j)$, at the $i$-th row from the top and the $j$-th column from the left, contains the character $S_{ij}$.
Consider creating a string of length $H+W-1$ by the following operation.
- First, prepare an empty string $T$ and stand on cell $(1,1)$.
-
Then, move according to the following rules.
- When you are on cell $(H,W)$, append the character $S_{HW}$ to the end of the string $T$ and end the operation.
-
Otherwise, when you are on cell $(i,j)$, append the character $S_{ij}$ to the end of the string $T$. Then, move to cell $(i+1,j)$ or $(i,j+1)$.
- However, when $i=H$, moving to $(i+1,j)$ is not allowed.
- Moreover, when $j=W$, moving to $(i,j+1)$ is not allowed.
There are ${}_{H+W-2}\mathrm{C}_{H-1}$ ways to move from cell $(1,1)$ to $(H,W)$. Among these, how many ways of moving produce a string that is a palindrome? Find the count modulo $10^9+7$.
Input
$H$ $W$
$S_{11}\ldots S_{1W}$
$\vdots$
$S_{H1}\ldots S_{HW}$
- $1\leq H,W\leq 200$
- $H,W$ are integers.
- $S_{ij}$ is a lowercase English letter.
Output
Output the total number of ways of moving that produce a palindrome, modulo $10^9+7$.
Sample
Sample 1
Input
3 3 abc cbc dca
Output
3
There are the following $6$ ways of moving.
- Moving as $(1,1)\to(1,2)\to(1,3)\to(2,3)\to(3,3)$ produces the string
abcca. - Moving as $(1,1)\to(1,2)\to(2,2)\to(2,3)\to(3,3)$ produces the string
abbca. - Moving as $(1,1)\to(1,2)\to(2,2)\to(3,2)\to(3,3)$ produces the string
abbca. - Moving as $(1,1)\to(2,1)\to(2,2)\to(2,3)\to(3,3)$ produces the string
acbca. - Moving as $(1,1)\to(2,1)\to(2,2)\to(3,2)\to(3,3)$ produces the string
acbca. - Moving as $(1,1)\to(2,1)\to(3,1)\to(3,2)\to(3,3)$ produces the string
acdca.
Sample 2
Input
4 4 abcd efgh ijkl mnop
Output
0
None of the obtained strings is a palindrome.
Sample 3
Input
20 20 aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa
Output
345263555
Output the answer modulo $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。