13391번 - 특별한 표

문제

준규는 정수가 채워져 있는 표를 매우 좋아한다. 준규는 다음과 같은 4가지 성질을 모두 만족하는 표를 특별한 표라고 한다.

• 표는 N행 M열로 이루어져 있다.
• 표의 각 칸에는 1보다 크거나 같고, C보다 작거나 같은 자연수가 하나 채워져 있다.
• 임의의 서로 다른 두 행 r1과 r2에 대해서, 서로 다른 수가 채워져 있는 칸 (r1, c)와 (r2, c)가 적어도 하나 존재한다.
• 임의의 서로 다른 두 열 c1과 c2에 대해서, 서로 다른 수가 채워져 있는 칸 (r, c1)와 (r, c2)가 적어도 하나 존재한다.

N, M, C가 주어졌을 때, 특별한 표의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, C (1 ≤ N, M, C ≤ 4,000)가 주어진다.

출력

특별한 표의 개수를 1,000,000,007로 나눈 나머지를 출력한다.

제한

힌트

예제 1의 경우에 가능한 특별한 표는 다음과 같다.

11 11 12 21 22 22 21 12 12 21
12 21 11 11 21 12 22 22 21 12