팰린드롬 경로 3

시간 제한1초메모리 제한256 MB

요약

오른쪽이나 아래쪽으로만 이동해 좌상단에서 우하단까지 가는 경로 중 글자가 회문이 되는 개수를 1000000007로 나눈 나머지로 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 행렬
정답자: 아직 제출이 없습니다

문제

$N \times N$ 농장 ( $1 \leq N \leq 500$ ) 각 칸에 대문자가 적혀 있다. 송아지는 $(1,1)$ 에서 $(N,N)$ 까지 오른쪽 또는 아래로만 이동한다. 경로에 적힌 글자열이 팰린드롬이면 길을 잃는다. 팰린드롬 경로의 개수를 $1{,}000{,}000{,}007$ 로 나눈 나머지를 구하라.

입력

첫 줄에 $N$ , 다음 $N$ 줄에 격자가 주어진다.

출력

팰린드롬 경로의 개수를 $1{,}000{,}000{,}007$ 로 나눈 나머지를 출력한다.

힌트

예제 $4 \times 4$ 격자의 답은 $12$ 이다.

예제4

예제 1
입력
```
4
ABCD
BXZX
CDXB
WCBA
```
예상 출력
```
12
```
예제 2
입력
```
2
AA
AA
```
예상 출력
```
2
```
예제 3
입력
```
3
ABC
DEF
GHI
```
예상 출력
```
0
```
예제 4
입력
```
2
AB
CD
```
예상 출력
```
0
```