== include(page="template/taskheader" task_id="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).

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

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

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

h2. Date de intrare

* $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ţiei pentru care x ~i~ ≠y ~i~.

* 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ţiei pentru care $x ~i~$ ≠y $~i~$.

h2. Exemplu