Bessie tem uma faixa de tela de $N$ unidades ($1 \leq N \leq 10^6$) e quer pintá-la, mas não conseguiu pincéis. No lugar deles, tem $M$ carimbos de borracha de cores diferentes ($1 \leq M \leq 10^6$), cada um de largura $K$ unidades ($1 \leq K \leq 10^6$). Maravilhada com as possibilidades, quer saber exatamente quantas pinturas diferentes pode criar carimbando em alguma ordem.
O carimbo deve ser alinhado com exatamente $K$ unidades vizinhas da tela. Não pode ultrapassar as extremidades nem cobrir frações de unidades. Pinta as $K$ unidades cobertas com sua cor. Cada carimbo pode ser usado várias vezes, uma ou nenhuma. Mas, quando Bessie terminar, toda unidade deve ter sido pintada ao menos uma vez.
Ajude Bessie a encontrar o número de pinturas diferentes módulo $10^9 + 7$. Pinturas visualmente idênticas feitas com sequências diferentes contam como a mesma.
Entrada
A única linha contém três inteiros $N$, $M$ e $K$. É garantido que $K \leq N$.
Saída
Um inteiro: o número de pinturas possíveis módulo $10^9 + 7$.
Exemplos
Entrada 1
3 2 2
Saída 1
6
Explicação
Se os dois carimbos têm cores A e B, as pinturas possíveis são AAA, AAB, ABB, BAA, BBA e BBB.
Subtarefas
Em pelo menos $75\%$ dos casos de entrada, $N,K \leq 10^3$.
Autor do problema: Dhruv Rohatgi