Consecutive lectures are hard (Easy)

Interview

Time limit1sMemory limit1024 MB

Summary

Count the timetables that include every mandatory period and whose longest run of consecutive chosen periods is exactly k, modulo 1e9+7.

Level: Medium5 of 10
Topics: Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

This problem is a subproblem of Consecutive lectures are hard (Hard), and you can get it accepted by submitting the correct solution to Hard.

Dohoon failed to register for courses last semester.

A school day has periods $1, 2, \ldots, n$ , and each of the $n$ distinct classes takes exactly one distinct period. In this registration, Dohoon wants to pick classes so that the longest run of consecutive classes is exactly $k$ periods long. The same run of $k$ periods may appear more than once.

Some of the possible cases for Sample 1.

In both cases, the longest run of consecutive classes is exactly 2 periods.

Some classes are mandatory, though. Take them into account and help Dohoon register!

Input

The first line contains two integers $n$ and $k$ , separated by a space.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ , separated by spaces. $a_i$ is 1 if the class in period $i$ is mandatory, and 0 otherwise.

Output

Print the number of timetables in which the longest run of consecutive classes is exactly $k$ periods among periods $1, 2, \ldots, n$ , modulo $10^9+7$ .

Constraints

$1 \le k \le n \le 3\,000$ .
$a_i = 0$ .

Examples1

Example 1
Input
```
5 2
0 0 0 0 0
```
Expected output
```
11
```