h2. Cerinţă

Determinaţi numărul coregrafiilor frumoase modulo $999983$ pentru o piesă, care: dureaza exact $k$ timpi muzicali, respectă condiţiile de mai sus şi sunt formate doar din cele n figuri cunoscute de D şi S (mai este prea puţin timp până la concurs, ca ei să inveţe şi figuri noi).

Determinaţi numărul coregrafiilor frumoase modulo $999983$ pentru o piesă, care: durează exact $k$ timpi muzicali, respectă condiţiile de mai sus şi sunt formate doar din cele $n$ figuri cunoscute de D şi S (mai este prea puţin timp până la concurs, ca ei să inveţe şi figuri noi).

h2. Date de intrare

h2. Restricţii şi precizări

* $n ≤ 100 000$
* $k ≤ 2 000 000 000$

* $n ≤ 100 000$.
* $k ≤ 2 000 000 000$.

* $k$ va fi întotdeauna divizibil cu $8$.

* $1 ≤ lungimea unei figuri ≤ 8$

* $1 ≤ lungimea unei figuri ≤ 8$.

* Pentru $30%$ din teste va exista o singură figură de o anumită lungime.
* Pentru $50%$ din teste $n ≤ 30$.
* Pentru $70%$ din teste lungimile figurilor vor fi numai valori din mulţimea ${2, 4, 6, 8}$.

h3. Explicaţie
Sunt $16$ timpi muzicali deci o coregrafie frumoasă se va dansa pe $16 / 8 = 2$ fraze muzicale.

Dacă notăm figurile cu litere, avem figura $A$ de lungime $1$, figura $B$ de lungime $1$ şi figura $C$ de lungime $8$. Prima frază muzicală poate fi alcătuită din orice secvenţă alcătuită din opt bucăţi de $A$ sau $B$, deci în total $28 = 256$ posibilităţi. Încă o posibilitate de alcătuire a primei fraze este printr-un singur $C$. Rezultă un total de $257$ posibilităţi. Pentru a doua frază avem tot atâtea posibilităţi, deci în total există $257 * 257 = 66049$ coregrafii frumoase posibile.
Cum $66049$ modulo $999983 = $66049$, se obţine rezultatul $66049$.

Dacă notăm figurile cu litere, avem figura $A$ de lungime $1$, figura $B$ de lungime $1$ şi figura $C$ de lungime $8$. Prima frază muzicală poate fi alcătuită din orice secvenţă alcătuită din opt bucăţi de $A$ sau $B$, deci în total $2^8^ = 256$ posibilităţi. Încă o posibilitate de alcătuire a primei fraze este printr-un singur $C$. Rezultă un total de $257$ posibilităţi. Pentru a doua frază avem tot atâtea posibilităţi, deci în total există $257 * 257 = 66049$ coregrafii frumoase posibile.
Cum $66049$ modulo $999983 = 66049$, se obţine rezultatul $66049$.

== include(page="template/taskfooter" task_id="tango") ==

4803