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

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.

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