33154번 - 데이터를 추가해 주세요. 스페셜 저지

문제

현빈이는 다이나믹 프로그래밍의 고수가 되고 싶어서 매일매일 백준에서 다이나믹 프로그래밍 문제를 푼다. 오늘도 어김없이 다이나믹 프로그래밍 문제를 찾던 현빈이는 다음과 같은 문제를 발견했다.

$N \times N$크기의 미로가 있다. 미로의 가장 왼쪽 위는 $(1, 1)$칸이고 가장 오른쪽 아래는 $(N, N)$칸이며 각 칸은 빈칸 또는 벽으로 구성된다. 시작점인 $(1, 1)$칸에서 출발해 도착점인 $(N, N)$칸에 도달하려 하는데 다음과 같은 규칙에 따라 이동하려 한다.

1. 현재 위치가 $(r, c)$칸 일 때, $(r, c+1)$이 빈칸이라면, $(r, c+1)$칸으로 이동할 수 있다.
2. 현재 위치가 $(r, c)$칸 일 때, $(r+1, c)$이 빈칸이라면, $(r+1, c)$칸으로 이동할 수 있다.
3. 현재 위치가 $(r, c)$칸 일 때, $(r+1, c)$칸과 $(r+2, c)$칸이 빈칸이라면, $(r+2, c)$칸으로 한 번에 이동할 수 있다.

미로의 시작점과 도착점은 항상 빈칸임이 보장될 때 시작점에서 출발해 도착점에 도달하는 이동 방법의 개수를 $M$으로 나눈 나머지를 출력한다. 단, 시작점에서 출발해 도착점에 도달할 수 없다면 $-1$을 출력한다.

문제를 보자마자 너무 간단한 다이나믹 프로그래밍 문제라고 생각한 현빈이는 신나서 1분 만에 코드를 작성했다. 현빈이가 작성한 코드의 의사코드는 다음과 같다.

function solve(N, M, Map):
 DP = [N + 1][N + 1] # 0으로 초기화된 (N + 1) x (N + 1) 크기의 DP 배열 선언
 DP[1][1] = 1 % M # 시작점 설정
 # '.'은 빈칸 '#'은 벽
 for r from 1 to N:
 for c from 1 to N:
 if Map[r][c] is '#':
 continue
 if r + 1 <= N and Map[r + 1][c] is '.':
 DP[r + 1][c] = (DP[r + 1][c] + DP[r][c]) % M # 이동 방법 1
 if c + 1 <= N and Map[r][c + 1] is '.':
 DP[r][c + 1] = (DP[r][c + 1] + DP[r][c]) % M # 이동 방법 2
 if r + 2 <= N and (Map[r + 1][c] and Map[r + 2][c]) is '.':
 DP[r + 2][c] = (DP[r + 2][c] + DP[r][c]) % M # 이동 방법 3
 if DP[N][N] is 0:
 DP[N][N] = -1
 return DP[N][N]

현빈이는 위와 같은 코드를 제출하고 맞았습니다!! 를 받았지만, 이를 옆에서 지켜보던 민우는 도착점에 도달할 수 있으며 이동 방법의 개수가 $M$의 배수라면 0ドル$을 출력해야 하는데 현빈이의 코드는 $-1$을 출력한다며 틀린 코드라고 지적했다. 현빈이의 코드를 틀리게 하는 데이터를 추가해 보자.

입력

첫 번째 줄에 양의 정수 $M$이 주어진다. (1ドル \le M \le 314,159円,265円$)

출력

첫 번째 줄에 미로의 크기를 나타내는 정수 $N$을 출력한다. (2ドル \leq N \leq 60$)

다음 $N$개의 줄에 걸쳐 .과 #로만 이루어진 미로를 나타내는 문자열을 출력한다. $i$ 번째 줄의 $j$ 번째 문자는 $(i, j)$칸의 상태를 나타내며, .이라면 빈칸을, #이라면 벽을 의미하고, 시작점과 도착점은 항상 빈칸이어야 한다.

제한

힌트