시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 512 MB63332553.191%

문제

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

- $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$

예제 입력 1

1 5

예제 출력 1

3 5
.....
..#..
.....

예제에선 이해를 돕기 위하여 $P = 5$ 로 설명하였다. 채점에서는 $P$ 는 $1,009$ 또는 $1,000,000,009$ 이다.

출처

Contest > 소프트콘 > 제3회 소프트콘 H번

채점 및 기타 정보

  • 예제는 채점하지 않는다.