Tractorel a renuntat(pe moment) la leii grei. Datorita valorii sale a fost capturat de greci.

Se dau $3$ numere $N$, $P$, $10000007$ si un alfabet $SIGMA$ $=$ ${'a', 'b', ...'z'}$ format din $26$ de litere.

Se dau $3$ numere $N$, $P$, $Mod$ si un alfabet $SIGMA$ $=$ ${'a', 'b', ...'z'}$ format din $26$ de litere.
Restrictionat de greci, Tractorel nu poate forma decat cuvinte de lungime N cu litere din alfabetul $SIGMA$ astfel incat oricare $2$ litere identice sa se afle la distanta cel putin $P$.

Fie un cuvant $c{~1~}c{~2~}...c{~N~}$. Definim distanta dintre $2$ litere $c[~i~]$, $c[~j~]$ ca fiind $|i - j|$.

Restrictionat de greci, Tractorel nu poate forma decat cuvinte de lungime $N$ cu litere din alfabetul $SIGMA$ astfel incat oricare $2$ litere identice sa se afle la distanta cel putin $P$.
 
Tractorel e in necaz mare, stiind ca Romania - Grecia se va termina $3-0$ va cere ajutorul sa numarati sirurile pe care le poate forma in prezenta grecilor.
Atentie! Din motive obscure, rezultatul se doreste a fi afisat modulo 10000007!

Tractorel e in necaz mare, stiind ca Romania - Grecia se va termina 3-0 va cere ajutorul
 

h2. Date de intrare

h2. Restricţii

* $1 ≤ N ≤ 10^15$
* $1 ≤ P ≤ N$

* $... ≤ ... ≤ ...$

h2. Exemplu