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

• 표는 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

2 2 2

예제 출력 1

10

예제 입력 2

1 1 4000

예제 출력 2

4000

예제 입력 3

2 3 5

예제 출력 3

13740

예제 입력 4

4000 1 4000

예제 출력 4

593395757

예제 입력 5

5 5 1

예제 출력 5

0

예제 입력 6

4000 4000 4000

예제 출력 6

237003303

힌트

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

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