Bessie는 길이 $N$ 단위의 캔버스 띠($1 \leq N \leq 10^6$)를 얻어 그림을 그리려 하지만 붓을 구하지 못했습니다. 대신 색이 서로 다른 $M$개의 고무 도장($1 \leq M \leq 10^6$)이 있으며 각각 너비가 $K$ 단위입니다($1 \leq K \leq 10^6$). 다양한 가능성에 놀란 Bessie는 어떤 순서로 도장을 찍어 서로 다른 그림을 정확히 몇 개 만들 수 있는지 궁금합니다.

도장은 캔버스의 정확히 $K$개의 인접한 단위에 맞추어야 합니다. 양 끝을 넘거나 단위의 일부만 덮을 수 없습니다. 덮인 $K$개의 단위를 도장 색으로 칠합니다. 각 도장은 여러 번, 한 번, 또는 전혀 쓰지 않아도 됩니다. 하지만 끝났을 때는 모든 단위가 적어도 한 번 칠해져 있어야 합니다.

Bessie를 도와 서로 다른 그림 수를 $10^9 + 7$로 나눈 나머지를 구하세요. 찍는 연산 순서가 달라도 모습이 같으면 같은 그림입니다.

입력

유일한 입력 줄에는 세 정수 $N$, $M$, $K$이 주어집니다. $K \leq N$가 보장됩니다.

출력

하나의 정수: 가능한 그림 수를 $10^9 + 7$로 나눈 나머지입니다.

예제

입력 1

3 2 2

출력 1

6

참고

두 도장의 색이 A와 B이면 가능한 그림은 AAA, AAB, ABB, BAA, BBA, BBB입니다.

서브태스크

입력 케이스의 적어도 $75\%$에서 $N,K \leq 10^3$입니다.

출제: Dhruv Rohatgi