背景

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

题目描述

给定简单无向图 $G=(V,E)$，其中 $V\subset \{1,2,\ldots,n\}$。

给定正整数 $k$。$G$ 中只有编号之差不大于 $k$ 的点间有连边。换言之，$(u,v)\in E\iff 1\le |u-v|\le k$。

定义 $G$ 的一条回路为一个长度为 $m=|V|$ 的序列 $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$ 中的每一个元素。

定义两条回路 $a,a'$ 本质相同，当且仅当它们循环同构。形式化地说，两条回路 $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}$。

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

输入格式

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

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

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

输出格式

输出一行一个整数，表示答案对 $(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$；
• $|V|+3\le n$。