시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 116 30 24 28.235%

문제

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

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

숌은 N * M 크기의 체스판에 K개의 룩을 놓는데, 서로 공격받지 않는 경우의 수를 구하는 문제를 생각했다. 이 문제는 너무 쉽게 풀려서 숌은 좀 더 어려운 문제를 찾다가 한 행이나 한 열에 최대 2개를 놓는 방법의 경우의 수가 궁금해지기 시작했다.

N*M 크기의 체스판이 주어졌을 때, K개의 룩을 체스판에 놓는데, 각 룩은 최대 1개의 룩에만 공격받는 경우의 수가 궁금해졌다. 어떤 룩은 공격받지 않을 수도 있다.

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

입력

첫째 줄에 체스판의 세로 크기 N, 둘째 줄에 가로 크기 M, 셋째 줄에 놓으려고 하는 룩의 수 K가 주어진다. N과 M과 K는 100보다 작거나 같은 자연수이다.

출력

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

예제 입력

2
3
3

예제 출력

6

힌트

XX.  X.X  .XX  ..X  .X.  X..
..X  .X.  X..  XX.  X.X  .XX

출처