题目简介

有一个长度为$N$的数列，其仅由$0,1$构成。

现在，有一些地方需要填充，这些地方用问号来代替。

需要知道，有几种方案来填充问号，使得无论从数列中取出怎样的连续的子数列，其子数列中所包含的$0$的个数和$1$的个数的差都必须在$K$以下。

输入格式

• 在第$1$行中，有两个正整数$N(1 \le N \le 300)$和$K(1 \le K \le N)$。这表示数列的长度为$N$，子数列允许的最大差为$K$。
• 第$2$行提供长度为$N$的字符串，表示这个数列。字符串仅由$0$、$1$和问号构成
  • 如果从左起$i$个字符是$0$，则表示随机数表的第$i$个元素必须是$0$。
  • 如果从左起$i$个字符是$1$，则表示随机数表的第$i$个元素必须是$1$。
  • 如果从左起第$i$个字符是问号，则随机数表的第$i$个元素是$0$和$1$都可以（也就是需要填充）。

输出格式

输出填充数列中问号的方案的总数对$10^9+7$取模，末尾要换行。