N-Rook II
시간 제한2초메모리 제한128 MB
N×M 체스판에 K개의 룩을 놓아 각 룩이 다른 룩에게 최대 한 번만 공격받도록 하는 배치 수를 1,000,001로 나눈 나머지로 구합니다.
문제
체스판의 한 칸에는 최대 하나의 룩을 놓을 수 있다. 룩은 같은 행이나 같은 열에 있는 다른 룩을 공격할 수 있다.
N × M 크기의 체스판에 K개의 룩을 놓으려고 한다. 각 룩을 공격할 수 있는 다른 룩의 수가 1개 이하가 되도록 놓는 방법의 수를 구하라. 공격하는 룩이 없는 경우도 허용된다.
입력
첫째 줄에 체스판의 세로 크기 N이 주어진다.
둘째 줄에 체스판의 가로 크기 M이 주어진다.
셋째 줄에 놓을 룩의 수 K가 주어진다.
출력
N × M 크기의 체스판에 K개의 룩을 놓는 방법 중, 각 룩을 공격할 수 있는 다른 룩이 최대 1개인 경우의 수를 1,000,001로 나눈 나머지를 출력한다.
제한
- 1 ≤ N, M ≤ 100
- 1 ≤ K ≤ 100