== include(page="template/taskheader" task_id="tango") ==
Poveste şi cerinţă...
Un tango este format din fraze muzicale, fiecare dintre acestea având $8$ timpi muzicali. Timpii muzicali au aceeaşi durată. La fel de importantă ca melodia unui tango este şi dansul asociat ei. Mişcările efectuate în timpul dansului se numesc figuri. Succesiunea de figuri efectuate în timpul dansului formează o coregrafie. Două coregrafii se consideră diferite dacă succesiunea figurilor care le alcătuiesc este diferită. O coregrafie frumoasă asociată unui tango are particularitatea următoare: atunci când se termină o frază muzicală trebuie să se termine şi o figură.
D şi S se pregătesc pentru primul lor concurs de dans şi ei lucreaza momentan la coregrafia de tango. Chiar dacă va fi primul lor concurs, ei deja ştiu $n$ figuri de dans şi au calculat pentru fiecare dintre aceste figuri câţi timpi muzicali durează. Fiindcă le place foarte mult să danseze împreună, ei vor să pregătească o coregrafie frumoasă pentru o piesă care durează exact $k$ timpi muzicali.
h2. Cerinţă
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
Fişierul de intrare $tango.in$ ...
Pe prima linie a fişierului de intrare $tango.in$ se află numerele naturale nenule $n$ şi $k$, separate printr-un singur spaţiu. Pe a doua linie se află exact $n$ numere separate prin câte un spaţiu, reprezintând lungimile figurilor.
h2. Date de ieşire
În fişierul de ieşire $tango.out$ ...
În fişierul de ieşire $tango.out$ se va afişa numărul de coregrafii posibile modulo $999983$.
h2. Restricţii
h2. Restricţii şi precizări
* $... ≤ ... ≤ ...$
* $n ≤ 100 000$.
* $k ≤ 2 000 000 000$.
* $k$ va fi întotdeauna divizibil cu $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}$.
* Prin $a$ modulo $b$ se înţelege restul împărţirii lui $a$ la $b$.
h2. Exemplu
table(example). |_. tango.in |_. tango.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 16
1 1 8
| 66049
|
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 $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") ==
