sir5

Sir5

== include(page="template/taskheader" task_id="sir5") ==

Poveste şi cerinţă...

Desi spera la o masinuta cu radiotelecomanda, Marian a primit de la Mos Craciun o problema. Revoltat, vrea sa ii trimita Mosului rezolvarea (alaturi de niste urari frumoase), insa pentru aceasta are nevoie de ajutorul vostru.
 
Se da un sir binar (format doar din caracterele $1$ si $0$) de lungime $N$ si trebuie sa plasati intervale inchise ($0$ sau mai multe) de lungime data $L$ peste acest sir, cu urmatoarele proprietati:
[x] oricare doua intervale nu se intersecteaza;
[x] intervalele vor fi complet incluse in sir (capetele nu au voie sa depaseasca extremitatile sirului);
[x] orice interval trebuie sa contina in interiorul sau cel putin un $1$;
[x] nu este obligatoriu ca fiecare element din sir sa fie acoperit de un interval.
 
Determinati in cate moduri se pot plasa aceste intervale peste sir, modulo $666013$.
 
Sirul va fi dat sub forma unei vector de elemente: $a[1] a[2] ... a[M]$, cu semnificatia: primele $a[1]$ elemente din sir au valoarea $1$, urmatoarele $a[2]$ elemente au valoarea $0$, urmatoarele $a[3]$ sunt $1$, urmatoarele $a[4]$ sunt $0$ si tot asa.

h2. Date de intrare

Fişierul de intrare $sir5.in$ ...

Fişierul de intrare $sir5.in$ contine pe prima linie doua numere naturale $M$ si $L$, despartite prin cate un spatiu, cu semnificatia din enunt. Pe a doua linie se gasesc $M$ numere naturale, despartite prin cate un spatiu, numere care reprezinta elementele vectorului $a$.

h2. Date de ieşire

În fişierul de ieşire $sir5.out$ ...

În fişierul de ieşire $sir5.out$ se va afla pe prima linie un singur numar natural, care semnifica numarul de moduri in care se pot amplasa intervale inchise de lungime $L$ peste sirul binar, cu proprietatile din enunt, modulo $666013$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $ 2 ≤ M ≤ 50 $
* $ 2 ≤ L ≤ 50 $
* $ 2 ≤ a[1] + a[2] + ... + a[M] ≤ 1.000.000.000 $

h2. Exemplu