题目描述

夏至祭是一场迎接祖灵于夏季归来同时祈求丰收的庆典。村里的男人会在广场上演出冬之军跟夏之军的战争，夏之军会打倒冬之军的大将冬男，再放火将他连山车一起烧掉。

谢尔吉斯村长已经选好了$\red{N}$个人参加演出，其中一些人负责演夏之军，另一些人负责演冬之军。由于人数众多，谢尔吉斯想把这$\red{N}$个人分成若干个连续的段。

为了保证演出的顺利进行，每段的夏之军人数与冬之军人数之差的绝对值不能超过$\red{K}$。

谢尔吉斯想知道符合条件的划分方案有多少种。由于符合条件的方案有很多，你只要输出方案数除以$\red{1e9+7}$的余数。

输入格式

第一行两个整数$\red{N,K，}$意义如题目描述所示。

接下来一行$\red{N}$个整数，第$\red{i}$个整数为$\red{0}$表示第$\red{i}$个人是夏之军，$\red{1}$表示第$\red{i}$个人是冬之军。

输出格式

一行一个整数，表示符合条件的方案数除以$\red{1e9+7}$的余数。

样例

输入样例

4 1
0 0 1 1

输出样例

5

提示

$\red{20\%}$的数据保证，$\red{N≤}$$\red{20}$。

$\red{50\%}$的数据保证，$\red{N≤}$$\red{8000}$。

另有$\red{15\%}$的数据保证，所有的人都是夏之军。

另有$\red{15\%}$ 的数据保证，$\red{K=0}$。

$\red{100\%}$的数据保证，$\red{1≤}$$\red{N≤}$$\red{10^5，}$$\red{0≤}$$\red{K<N}$。