시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 14 14 5 100.000%

문제

준규는 정수가 채워져 있는 표를 매우 좋아한다. 준규는 다음과 같은 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로 나눈 나머지를 출력한다.

예제 입력

2 2 2

예제 출력

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