레이팅 미적용설명
농부 존의 농장은 N x N 격자 모양의 밭(1 <= N <= 500)으로 이루어져 있으며, 각 밭에는 A..Z 중 한 글자가 적혀 있다.
매일 베시는 왼쪽 위 밭에서 오른쪽 아래 밭까지 걸어가며, 한 걸음마다 오른쪽으로 한 칸 또는 아래로 한 칸 이동한다. 베시는 자신이 만들어 내는 문자열을 기록하는데, 이 문자열이 팰린드롬이면 방향 감각을 잃는다.
팰린드롬에 대응되는 서로 다른 경로의 개수를 구해 베시를 도와주자. 같은 팰린드롬을 만드는 서로 다른 경로는 여러 번 센다. 답을 1,000,000,007로 나눈 나머지를 출력한다.
제약
입력 형식
첫째 줄에 N이 주어진다. 나머지 N개의 줄에는 격자의 N개 행이 주어지며, 각 행은 A..Z 범위의 문자 N개로 이루어져 있다.
출력 형식
베시가 택할 수 있는 서로 다른 팰린드롬 경로의 개수를 1,000,000,007로 나눈 나머지를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
palpath.in · 출력을 쓸 파일 palpath.out예제 1
입력
4
ABCD
BXZX
CDXB
WCBA출력
12설명
Output details: 1x ABCDCBA, 1x ABCWCBA, 6x ABXZXBA, 4x ABXDXBA = 12 routes.
문제 정보
태그