1767번 - N-Rook II

체스 세계랭킹 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