ikebana

O florărie vrea să ajungă în Guinness book cu cel mai mare aranjament floral. Ei au la dispoziţie t tipuri de flori, dintre care patru tipuri sunt mai speciale: gerbera, orhideea, azaleea şi hortensia. Lucrătorii au hotărât să pună florile distanţate uniform pe mai multe rânduri, pe fiecare rând exact n flori. Nu vor exista două rânduri identice, dar toate rândurile vor respecta anumite cerinţe:

• Ei au observat că hortensiile au o viaţă mult mai îndelungată, dacă se învecinează pe acelaşi rând cu o azalee şi cu o orhidee, indiferent dacă ordinea este azalee-hortensie-orhidee sau orhidee-hortensie-azalee.
• Gerberele vor fi amplasate în aşa fel încât între oricare două gerbere să existe cel puţin p flori, tipul lor fiind oricare dar nu gerbera.

De exemplu dacă avem la dispoziţie t=5 tipuri de flori: azalee (notate cu a), hortensii (notate cu h), orhidee (notate cu o), gerbere (notate cu g), şi begonii (notate cu b), între două gerbere se vor amplasa minim p=3 flori, iar rândul va fi format din n=6 flori, atunci următoarele aranjamente florale sunt corecte: aoaaoo, ahohag, gbbbgo, gbbbog, bbbbbb.

Următoare aranjamente nu sunt însă corecte: ohoaha (hortensiile nu sunt între o orhidee şi o azalee), gogbao (cele două gerbere nu sunt despărţite de minim trei flori), ahohah (ultima hortensie nu se învecinează cu o orhidee).

Pentru n=6, p=3, t=5, numărul diferitelor aranjamente florale este 2906.

Cerinţă

Cunoscând valorile lui n, p şi t, să se determine numărul liniilor distincte ce se pot obţine cu cerinţele de mai sus.

Date de intrare

Fişierul ikebana.in conţine pe un singur rând 3 numere naturale n, p şi t separate prin câte un spaţiu.
n - reprezintă numărul de flori de pe un rând;
p - numărul minim de flori ce trebuie să despartă două gerbere dintr-un rând;
t - numărul tipurilor de flori distincte ce stau la dispoziţia florăriei.

Date de ieşire

Fişierul ikebana.out va conţine pe unicul rând un singur număr: numărul de aranjări distincte modulo 666013.

Restricţii

• 1 ≤ n ≤ 1.000.000.000;
• 3 ≤ p ≤ 20;
• 4 ≤ t ≤ 20;

Exemple

ikebana.in

6 3 5 

ikebana.out

2906

Explicaţii

Numărul aranjamentelor distincte este de 2906

ikebana.in

10 6 8 

ikebana.out

620160

Explicaţii

Numărul aranjamentelor distincte este de 181775696, şi avem: 181775696 % 666013 = 620160