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).

Cerinţă

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 şi precizări:

• $1 ≤ X ≤ min(K, 10^5)$
• $1 ≤ N, K ≤ 10^{15}$
• Pentru 10% din teste se garantează N, K, X ≤ 7.
• Pentru 30% din teste se garantează N ≤ 10000, K ≤ 100.
• Pentru 60% din teste se garantează K ≤ 100.
• Pentru 85% din teste se garantează K ≤ 1000.
• 2 şiruri $A=(x_1, x_2, …, x_n)$ şi $B=(y_1, y_2, .., y_n)$ sunt distincte dacă există cel putin o poziție i pentru care $x_i≠y_i$.

Exemplu:

xnumere.in

2 2 4

xnumere.out

14

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)

xnumere.in

10 6 8 

xnumere.out

258420