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.

* oricare doua intervale nu se intersecteaza;
* intervalele vor fi complet incluse in sir (capetele nu au voie sa depaseasca extremitatile sirului);
* orice interval trebuie sa contina in interiorul sau cel putin un $1$;
* 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$.