题目背景

译自 Izborne Pripreme 2017 (Croatian IOI/CEOI Team Selection) D1T1。$\texttt{2s,0.5G}$。

题目描述

给定简单无向图 $G=(V,E)$，其中 $|V|=n$。

给定点集 $S\subset V$，称 $S$ 中的点被删除。

给定正整数 $k$，则 $(u,v)\in E\iff u,v\in V\backslash S \land 0\lt |u-v|\le k$。

定义 $G$ 的一条回路为一个长度为 $m=|V|-|S|$ 的序列 $a_0,a_1,\cdots,a_{m-1}$，其中 $\forall 0\le i\lt m$，都有 $(a_i,a_{(i+1)\bmod m})\in E$，且 $a_0,a_1,\cdots,a_{m-1}$ 恰好取遍 $V\backslash S$ 中的每一个元素。

定义两条回路 $a,a'$ 本质相同，当且仅当存在非负整数 $k$，使得 $a_0=a'_{k\bmod m},a_1=a'_{(1+k)\bmod m},\cdots,a_{m-1}=a'_{(m-1+k)\bmod m}$。换句话说，$a$ 和 $a'$ 本质相同当且仅当 $a,a'$ 循环同构。

求出 $G$ 中本质不同的回路条数，对 $(10^9+7)$ 取模。

输入格式

第一行，两个正整数 $n,k$。

第二行，一个长度为 $n$ 的 $\texttt{01}$ 串 $s$。当且仅当 $s_i=1$ 时，$i\in S$。

保证 $|S|+3\le |V|$。

输出格式

输出一行一个整数，表示答案对 $(10^9+7)$ 取模后的结果。

6 3
100010

2

8 4
10000001

72

10 5
0010000100

428

提示

对于 $100\%$ 的数据，保证：

• $1\le n\le 100$；
• $3\le k\le 5$；
• $|S|+3\le |V|$。