Pittura con timbri

Bessie è entrata in possesso di una striscia di tela lunga $n$ unità e intende dipingerla. Tuttavia, non è riuscita a procurarsi alcun pennello. Al loro posto ha $m$ timbri di gomma di colori diversi, ciascuno largo $k$ unità. Stupita dalle possibilità che le si aprono davanti, Bessie vuole sapere esattamente quanti dipinti diversi potrebbe creare applicando i timbri sulla tela in un certo ordine.

Per usare un timbro, Bessie deve prima allinearlo con esattamente $k$ unità consecutive della tela. Il timbro non può sporgere oltre le estremità della tela, né può coprire frazioni di unità. Una volta applicato, il timbro colora le $k$ unità coperte con il proprio colore. Ogni timbro può essere usato più volte, una sola volta o mai. Tuttavia, quando Bessie avrà finito, ogni unità della tela dovrà essere stata colorata almeno una volta.

Aiuta Bessie a trovare il numero di dipinti diversi che potrebbe creare, modulo 10^9 + 7. Due dipinti dall'aspetto identico sono considerati uguali, anche se sono stati ottenuti con sequenze diverse di timbrature.