== include(page="template/taskheader" task_id="ikebana") ==
Poveste şi cerinţă...
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$.
h2. 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.
h2. Date de intrare
Fişierul de intrare $ikebana.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $ikebana.out$ ...
Fişierul $ikebana.out$ va conţine pe unicul rând un singur număr: numărul de aranjări distincte modulo $666013$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n ≤ 1.000.000.000$
* $3 ≤ p ≤ 20$
* $4 ≤ t ≤ 20$
h2. Exemplu
table(example). |_. ikebana.in |_. ikebana.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 3 5
| 2906
|
table(example). |_. ikebana.in |_. ikebana.out |
| 10 6 8
| 620160
|
h3. Explicaţie
...
În al doilea exemplu numărul aranjamentelor distincte este de $181775696$, şi avem: $181775696 % 666013 = 620160$
== include(page="template/taskfooter" task_id="ikebana") ==
