Säilytysfirmassa on ongelma. Firman $n$:stä asiakkaasta jokainen on tuonut säilytettäväksi yhden tavaran kutakin $m$:ää tavaratyyppiä. Nyt kuitenkin tavarat ovat sekoittuneet, ja saman tyyppisistä tavaroista ei enää voi tietää, mikä niistä on kenenkin. Kuinka monella tavalla tavarat voi jakaa takaisin asiakkaille niin, että täsmälleen $k$ asiakasta saa kaikki omat tavaransa takaisin?

Anna vastaus modulo $10^9 + 7$.

Syöte

Syötteessä ovat kokonaisluvut $n$, $m$ ja $k$.

Tuloste

Yksi kokonaisluku: mahdollisten jakojen lukumäärä.

Rajat

• $1 \le n \le 10^6$
• $1 \le m \le 10^9$
•  $0 \le k \le n$

Esimerkki

Syöte:

3 2 1

Tuloste:

9