== include(page="template/taskheader" task_id="marfa2") ==
Poveste şi cerinţă...
Maxi a deschis un magazin de mobilă secănd şi are multe comenzi de dulapuri pe care le transportă cu o maşină învechită (e o maşină secănd). Maşina este concepută special pentru a transporta dulapuri grele. Remorca maşinii este împărţită în două părţi (stanga si dreapta). Maşina e aşa de veche încât dacă timp de $k$ zile consecutive o parte a maşinii (stânga sau dreapta) este folosită continuu, se rupe osia pe acea parte. În continuare spunem că rezistenţa maşinii este $k$. Maşina poate transporta $0, 1$ sau $2$ dulapuri pe zi şi transporturile vor fi planificate în aşa fel ca maşina să nu se strice.
În oraşul lui Maxi o săptămână are $n$ zile, iar comenzile de transport se repetă identic în fiecare săptămână. De exemplu: rezistenţa maşinii este $k=3$, o săptămână are $n=8$ zile, iar comanda săptămânală distribuită pe zile este: $1, 2, 1, 0, 1, 1, 2, 1$.
h2. Cerinta
Aflaţi în câte moduri modulo $40099$ se pot planifica transporturile pe $z$ zile date, dacă se cunoaşte rezistenţa $k$ a maşinii, numărul $n$ al zilelor din săptămână, respectiv şirul comenzilor săptămânale.
h2. Date de intrare
Fişierul de intrare $marfa2.in$ ...
Fişierul $marfa2.in$ conţine pe prima linie două numere naturale $z$ şi $k$ cu semnificaţiile de mai sus. Pe linia a doua se găseşte numărul $n$ al zilelor din săptămână. Pe linia a treia sunt scrise $n$ numere naturale de valori $0, 1$ sau $2$ separate prin spaţiu, reprezentând comanda săptămânală de mobilă.
h2. Date de ieşire
În fişierul de ieşire $marfa2.out$ ...
Fişierul $marfa2.out$ va conţine un singur număr natural, numărul planificărilor corecte distincte modulo $40099$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $3 ≤ k ≤ 4$
* $5 ≤ n ≤ 19$
* $1 ≤ z ≤ 2 000 000 000$
* Atentie! O parte a maşinii (stânga sau dreapta) poate transporta un singur dulap într-o zi.
h2. Exemplu
table(example). |_. marfa2.in |_. marfa2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 3
5
1 0 2 2 0
| 4
|
h3. Explicaţie
...
Se cere numărul planificărilor pe $6$ zile, cu rezistenţa maşinii $k=3$ zile. Săptămâna are $5$ zile.
Pentru comanda $1 0 2 2 0 1$ avem $4$ planificări posibile (comanda din ziua $6$ este $1$, la fel ca şi prima zi, pentru că se reia săptămâna).
== include(page="template/taskfooter" task_id="marfa2") ==
