Consecutive Classes Are Tough (Hard)

Time limit1sMemory limit1024 MB

Summary

Given n periods where some classes are required, count the 0/1 timetables whose longest run of consecutive classes is exactly k, modulo 1e9+7.

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

Problem

This problem is the harder version of Consecutive Classes Are Tough (Easy), and you can get it accepted by submitting the correct code for this problem to Consecutive Classes Are Tough (Easy).

Dohoon failed to register for courses last semester.

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

However, some required classes must be taken. Consider the required classes and help Dohoon with his registration!

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 required, and $0$ otherwise.

Output

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

Constraints

$1\le k\le n\le 10^6$ .
$a_i\in\{0,1\}$ .

Examples2

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