22980번 - 테스트케이스 만들기 서브태스크스페셜 저지

문제

승주는 대회에 쓰일 대회 문제를 만들었다. 문제는 아래와 같다.

- $N \times M$ 격자판이 주어진다.

- 각 칸은 블럭 ('#') 이거나 빈 공간 ('.') 이다.

- 오른쪽 또는 아래 쪽으로만 갈 수 있다. 블럭이 있는 곳은 지나갈 수 없다.

- 왼쪽 상단에서 출발하여 오른쪽 하단으로 가는 방법의 수를 $P$ 로 나눈 나머지 $K$를 구하여라. (왼쪽 상단 또는 오른쪽 하단이 블럭으로 되어 있는 경우 방법의 수는 0이다.)

예를 들면

3 5 5 (N, M, P)
.....
..#..
.....

의 방법의 수는 6이므로 답은 $K=1$ 이 된다.

현태는 장난을 좋아해서 입력 파일의 격자판을 지워버렸다. 그래서 $K$ 랑 $P$ 밖에 모른다.

$K,ドル $P$ 가 주어지면 조건을 만족하는 격자판을 만들어보자.

입력

첫 번째 줄에 $K, P \; (0 \leq K < P)$ 가 주어진다.

출력

문제의 조건을 만족하는 테스트케이스가 없다면 첫 번째 줄에 $-1$ 만 출력한다.

테스트케이스가 있다면 첫 번째 줄에 $N,ドル $M$ 을 출력한다. 단, 파일이 너무 크면 안되므로 (1ドル \leq N, M, N+M \leq 100 $) 을 만족해야 한다.

두 번째 줄부터 $N$ 개의 줄에 격자판을 나타내는 문자열을 출력한다.

제한

서브태스크 1 (42점)

$P = 1,009$

서브태스크 2 (83점)

$P = 1,000,000,009$

힌트