도장 찍기

베시는 길이가 $N$인 띠 모양 캔버스를 손에 넣었고($1 \leq N \leq 10^6$), 여기에 그림을 그리려고 한다. 그런데 붓을 구하지 못했다. 붓 대신 색이 서로 다른 고무 도장 $M$개가 있고($1 \leq M \leq 10^6$), 도장은 모두 폭이 $K$칸이다($1 \leq K \leq 10^6$). 베시는 도장을 원하는 순서로 찍어서 만들 수 있는 그림이 모두 몇 가지인지 알고 싶다.

도장을 찍으려면 캔버스에서 이웃한 $K$칸에 정확히 맞춰야 한다. 도장이 캔버스 밖으로 나갈 수 없고, 한 칸의 일부만 덮을 수도 없다. 도장을 찍으면 덮인 $K$칸이 그 도장의 색으로 칠해진다. 같은 도장을 여러 번 찍어도 되고, 한 번만 찍어도 되고, 아예 찍지 않아도 된다. 다만 베시가 작업을 끝냈을 때 캔버스의 모든 칸은 적어도 한 번은 칠해져 있어야 한다.

만들 수 있는 그림이 몇 가지인지 세어 $10^9 + 7$로 나눈 나머지를 구하라. 찍은 순서가 달라도 완성된 모습이 같으면 같은 그림으로 센다.

첫째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $K \leq N$임이 보장된다.

만들 수 있는 그림의 가짓수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

$N = 3$, $M = 2$, $K = 2$이고 두 도장의 색이 A와 B라면, 만들 수 있는 그림은 AAA, AAB, ABB, BAA, BBA, BBB로 6가지다.