Fişierul intrare/ieşire:	ikebana.in, ikebana.out	Sursă	ONI 2011, clasele 11-12
Autor	Zoltan Szabo	Adăugată de	Gabriel Bitis •gabitzish1
Timp execuţie pe test	0.225 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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

Exemplu

Explicaţie

În al doilea exemplu numărul aranjamentelor distincte este de 181775696, şi avem: 181775696 % 666013 = 620160

Cum se trimit solutii?