Jovica je zaljubljenik u kriptografiju i odlučio je napisati tajnu poruku. Napisao je rečenicu i svaki znak pretvorio u niz bitova iste duljine. Zatim je uklonio sve vodeće nule svakog znaka, tako da je prvi bit svakog znaka postao 1, i na kraju ih je spojio u jedan dugačak string.

Tvoj zadatak je pomoći dekodirati ovu tajnu poruku. Znaš da su znakovi prije uklanjanja nula imali najviše \(k\) bitova i da nijedan znak nije bio kodiran kao sve nule.

Zadatak

Na koliko načina možeš dekodirati ovaj dani niz bitova duljine \(n\)? Ispiši broj načina modulo \(10^9 + 7\).

Podzadatci

Ulazni podatci

U prvom retku su dana dva broja \(n\) i \(k\), (\(k \leq n < 1000\)).

U sljedećem retku nalazi se string od \(n\) nula i jedinica.

Izlazni podatci

U jednom retku treba ispisati jedan broj, broj načina modulo \(10^9 + 7\).

Primjeri

Ulaz primjera 1

5 3
11111

Izlaz primjera 1

13

Ulaz primjera 2

6 3
111011

Izlaz primjera 2

8

Objašnjenje primjera 2

Validne rečenice su

1-1-10-1-1
11-10-1-1
1-110-1-1
1-1-101-1
11-101-1
1-1-10-11
11-10-11
1-110-11

Ulaz primjera 3

9 4
101010101

Izlaz primjera 3

8

Objašnjenje primjera 3

Validne rečenice su

10-10-10-10-1
1010-10-10-1
10-1010-10-1
10-10-1010-1
1010-1010-1
10-10-10-101
1010-10-101
10-1010-101