P11285 [COTS 2017] 周期 Ciklusi

译自 [Izborne Pripreme 2017 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2017/) 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$。当且仅当 $s_i=1$ 时，$i\in V$。 保证 $|V|+3\le |n|$。

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

对于 $100\%$ 的数据，保证： - $1\le n\le 100$； - $3\le k\le 5$； - $|V|+3\le n$。 | 子任务编号 | $n\le $ | $k\le $ |得分 | | :--: | :--: | :--: | :--: | | $ 1 $ | $ 20 $ | $5$ | $ 10 $ | | $ 2 $ | $ 100 $ | $3$ | $ 40 $ | | $ 3 $ | $ 100 $ | $5$ | $ 50 $ |