Se consideră şirurile formate din N numere întregi de la 1 la K, cu proprietatea că şirul conţine exact X numere distincte.
Cerinţă
Determinaţi numărul de şiruri distincte de lungime N cu elemente 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 o singură linie pe care va fi scris un număr natural reprezentând rezultatul modulo 666013.
Restricţii
• 1 ≤ X ≤ min(K, 105)
• 1 ≤ N, K ≤ 1015
• Două şiruri A=(x1,x2,…,xn) şi B=(y1,y2,...,yn) sunt distincte dacă există cel puţin o poziţie i pentru care xi≠yi.
Exemple
xnumere.in
xnumere.out
Explicaţii
2 2 4
14
Ş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)
