연강은 힘들어(Hard)

이 문제는 연강은 힘들어(Easy)의 상위 문제이고, 연강은 힘들어(Easy)에 이 문제의 정답 코드를 제출하여 맞힐 수 있다.

도훈이는 저번 학기 수강신청에 실패했다.

하루 일과는 $1,2,\ldots,n$교시로 구성되고, $n$개의 서로 다른 수업이 각각 하나의 서로 다른 교시를 차지한다. 이번 수강신청에서는 수강할 수업을 골라서 가장 많이 연속된 수업들이 정확히 $k$교시를 이루도록 시간표를 짜고 싶다. $k$교시짜리 연속 수업 묶음이 여러 번 나와도 상관없다.

하지만 반드시 수강해야 하는 필수 수업이 있다. 필수 수업을 고려하여 도훈이의 수강신청을 도와주자!

첫 번째 줄에 두 정수 $n$, $k$가 공백으로 구분되어 주어진다.

두 번째 줄에 각 교시의 필수 수업 여부를 나타내는 $n$개의 정수 $a_1,a_2,\ldots,a_n$이 공백으로 구분되어 주어진다. $a_i$는 $i$교시의 수업이 필수 수업이면 $1$, 아니면 $0$이다.

하루 $1,2,\ldots,n$교시 중 가장 많이 연속된 수업들이 정확히 $k$교시를 이루는 시간표의 가짓수를 $10^9+7$로 나눈 나머지를 출력한다.

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