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 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 ≤ 1000000000
• 3 ≤ p ≤ 20
• 4 ≤ t ≤ 20
Exemple
ikebana.in
ikebana.out
Explicaţii
6 3 5
2906
Numărul aranjamentelor distincte este de 2906
10 6 8
620160
Numărul aranjamentelor distincte este de 181775696, şi avem:
181775696 % 666013 = 620160