Fişierul intrare/ieşire:	xnumere.in, xnumere.out	Sursă	ONI 2013 Clasele 11-12
Autor	Bogdan-Cristian Tataroiu, Dragos Alin Rotaru	Adăugată de	Popescu Silviu •crushack
Timp execuţie pe test	0.5 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Xnumere

Din când în când un turist se gândeşte la o problemă dificilă (sau mai multe). Găseşte pe drum un şir de N numere intregi de la 1 la K. În călătoria spre regăsirea sinelui, fiecare şir conţine exact X numere distincte din mulţimea {1...K}. La sfârşitul călătoriei sale trage linia şi vede numărul de şiruri distincte. Bucuros că a reuşit să numere şirurile, vrea să vadă dacă şi voi puteţi găsi răspunsul la problema sa (simplă, de altfel).

Cerinta

Determina ţi numărul de şiruri distincte de lungime N cu toate numerele din mulţimea {1..K}, fiecare şir având exact X elemente distincte

Date de intrare

Fişierul xnumere.in va conţine pe prima linie trei numere naturale: K X N.

Date de ieşire

Fişierul xnumere.out va conţine un singur număr natural reprezentând răspunsul dat întrebării unui turist oarecare. Rezultatul va fi scris in fişier modulo 666013 .

Restricţii

• 1 ≤ X ≤ min(K,10⁵)
• 1 ≤ N,K ≤ 10¹⁵
• Pentru 10% din teste se garantează N, K, X ≤ 7.
• Pentru 30% din teste se garantează N ≤ 10000, K ≤ $00.
• Pentru 60% din teste se garantează K ≤ 100.
• Pentru 85% din teste se garantează K ≤ 1000.
• 2 şiruri A=( x ₁, x ₂,…, x _n)şi B=( y ₁, y ₂,.., y _n)sunt distincte dacă există cel putin o poziţiei pentru care x _i ≠y _i.

Exemplu

Explicaţie

Şirurile sunt:
(1,1,1,2),(1,1,2,1),(1,1,2,2),(1,2,1,1),(1,2,1,2),(1,2,2,1),(1,2,2,2),(2,1,1,1),(2,1,1,2),(2,1,2,1),(2,1,2,2),(2,2,1,1),(2,2,1,2),(2,2,2,1)

Cum se trimit solutii?