Add Test Data

Hyunbin wants to become an expert in dynamic programming, so he solves dynamic programming problems on an online judge every day. As usual, he was searching for one when he found the following problem.

There is an $N \times N$ maze. The top-left cell is $(1, 1)$ and the bottom-right cell is $(N, N)$. Each cell is either empty or a wall. Starting from $(1, 1)$, you want to reach $(N, N)$ by following these rules.

1. When the current position is $(r, c)$, if $(r, c+1)$ is empty, you can move to $(r, c+1)$.
2. When the current position is $(r, c)$, if $(r+1, c)$ is empty, you can move to $(r+1, c)$.
3. When the current position is $(r, c)$, if $(r+1, c)$ and $(r+2, c)$ are both empty, you can move to $(r+2, c)$ in one step.

The start and the end cells are always empty. Print the number of ways to get from the start to the end, modulo $M$. If the end cannot be reached from the start, print $-1$.

As soon as he saw it, Hyunbin thought it was a very simple dynamic programming problem, and he wrote the code in one minute. The pseudocode of his code is below.

function solve(N, M, Map):
    DP = [N + 1][N + 1]  # declare a DP array of size (N + 1) x (N + 1), filled with 0
    DP[1][1] = 1 % M  # set the start

    # '.' is an empty cell, '#' is a wall
    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  # move type 1

            if c + 1 <= N and Map[r][c + 1] is '.':
                DP[r][c + 1] = (DP[r][c + 1] + DP[r][c]) % M  # move type 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  # move type 3

    if DP[N][N] is 0:
        DP[N][N] = -1

    return DP[N][N]

His code was accepted, but Minwoo pointed out that it is wrong. If the end can be reached and the number of ways is a multiple of $M$, the answer should be $0$, but Hyunbin's code prints $-1$. Add test data that makes Hyunbin's code fail.

The first line contains a positive integer $M$ ($1 \le M \le 314\,159\,265$).

On the first line, print an integer $N$ ($2 \leq N \leq 60$), the size of the maze.

On the next $N$ lines, print the maze as strings made only of . and #. The $j$-th character of the $i$-th line gives the state of cell $(i, j)$. . means an empty cell and # means a wall. The start and the end cells must be empty.