민혁이는 \(N\) 개의 칸이 한 줄로 늘어선 울타리를 색칠하려고 한다. 사용할 수 있는 색은 모두 \(M\) 가지이며, 각 색에는 \(1\) 부터 \(M\) 까지의 번호가 붙어 있다.

칠하기는 다음 두 조건을 모두 만족해야 한다.

• 인접한 두 칸은 서로 다른 색으로 칠한다.
• 울타리 전체에서 정확히 \(K\) 가지 색만 사용한다. (고른 \(K\) 가지 색은 모두 적어도 한 번씩 등장해야 하고, 그 외의 색은 한 번도 쓰이지 않는다.)

이러한 칠하기 방법의 수를 큰 소수 \(1\,000\,000\,007\) 로 나눈 나머지를 구하여라.

예를 들어 \(N = 3\), \(M = 3\), \(K = 2\) 라면, 세 색 중 두 색을 고르는 \(\binom{3}{2} = 3\) 가지 방법 각각에 대해, 고른 두 색 \(A, B\) 로 인접이 다르게 칠하면서 둘 다 쓰는 방법은 \(ABA\), \(BAB\) 의 두 가지이다. 따라서 답은 \(3 \times 2 = 6\) 이다.

\(1 \le N \le 10^9\)

\(1 \le M \le 10^9\)

\(1 \le K \le \min(M, 100)\)

첫째 줄에 세 정수 \(N\), \(M\), \(K\) 가 공백으로 구분되어 주어진다.

조건을 만족하는 칠하기 방법의 수를 \(1\,000\,000\,007\) 로 나눈 나머지를 한 줄에 출력한다.

riseoj 작성

출처 Original