N-Rook II

체스판의 한 칸에는 최대 하나의 룩을 놓을 수 있다. 룩은 같은 행이나 같은 열에 있는 다른 룩을 공격할 수 있다.

N × M 크기의 체스판에 K개의 룩을 놓으려고 한다. 각 룩을 공격할 수 있는 다른 룩의 수가 1개 이하가 되도록 놓는 방법의 수를 구하라. 공격하는 룩이 없는 경우도 허용된다.

첫째 줄에 체스판의 세로 크기 N이 주어진다.

둘째 줄에 체스판의 가로 크기 M이 주어진다.

셋째 줄에 놓을 룩의 수 K가 주어진다.

N × M 크기의 체스판에 K개의 룩을 놓는 방법 중, 각 룩을 공격할 수 있는 다른 룩이 최대 1개인 경우의 수를 1,000,001로 나눈 나머지를 출력한다.

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