시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB88034826942.834%

문제

체스 세계랭킹 1위의 숌은 더 이상 체스를 대결할 상대가 없자, 새로운 체스방법을 생각했다.

일단 Rook은 체스판의 같은 열, 혹은 같은 행에 다른 말이 있을 경우, 그 말을 공격할 수 있는 말이다.

숌은 N * M 크기의 체스판에 K개의 룩을 놓는데, 서로 공격받지 않는 경우의 수를 구하는 문제를 생각했다. 이 문제는 너무 쉽게 풀려서 숌은 좀 더 어려운 문제를 찾다가 각 룩이 최대 1개의 룩에만 공격받는 경우의 수가 궁금해졌다. 어떤 룩은 공격받지 않을 수도 있다.

N*M크기의 체스판이 주어졌을 때, K개의 룩을 놓을 때, 각 룩이 최대 1개의 룩에만 공격받는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 체스판의 세로 크기 N, 둘째 줄에 가로 크기 M, 셋째 줄에 놓으려고 하는 룩의 수 K가 주어진다.

출력

N * M 크기의 체스판에 K개의 룩을 놓을 때, 각 룩이 최대 1개의 룩에만 공격받는 경우의 수를 1,000,001로 나눈 나머지를 출력한다.

제한

  • 1 ≤ N, M ≤ 100
  • 1 ≤ K ≤ 100

예제 입력 1

2
3
3

예제 출력 1

6
XX.  X.X  .XX  ..X  .X.  X..
..X  .X.  X..  XX.  X.X  .XX

예제 입력 2

4
5
2

예제 출력 2

190

예제 입력 3

6
7
20

예제 출력 3

0

예제 입력 4

23
37
39

예제 출력 4

288688

출처

  • 문제를 번역한 사람: baekjoon
  • 어색한 표현을 찾은 사람: dotorya