32220번 - 연강은 힘들어(Easy)

문제

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

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

하루 일과는 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 3,円 000$.
• $a_i=0$.

힌트