CF757D Felicity's Big Secret Revealed

道馆训练师们被 Felicity 训练营中发生的进化现象深深吸引，于是他们对宝可梦进化的秘密产生了好奇。 训练营的组织者给道馆训练师们提供了一个 PokeBlock，这是一串长度为 $n$ 的原料。每种原料类型只能是 $0$ 或 $1$。现在，组织者告诉道馆训练师们，要想让类型为 $k$（$k \geq 2$）的宝可梦进化，必须在 PokeBlock 上恰好做出 $k$ 个有效切割，将其分割为若干小块。 假设给定的 PokeBlock 序列为 $b_0 b_1 b_2 \cdots b_{n-1}$。你可以在 $n+1$ 个位置切割，也就是：$b_0$ 之前，$b_0$ 和 $b_1$ 之间，$b_1$ 和 $b_2$ 之间，……，$b_{n-2}$ 和 $b_{n-1}$ 之间，以及 $b_{n-1}$ 之后。 这 $n+1$ 个可选切割点记作（“|” 表示可切割处）： $|\ b_0\ |\ b_1\ |\ b_2\ |\ \cdots\ |\ b_{n-2}\ |\ b_{n-1}\ |$ 假设进行了 $k$ 个切割。则每对相邻切割点间会包含一段原料序列，这些序列就被看作二进制字符串。第一个切割点之前和最后一个切割点之后的原料会被丢弃（即不计入结果）。因此，共会得到恰好 $k-1$ 个二进制子串。每个这样的子串都可以看作一个二进制数。令 $m$ 表示这些子串所对应数字的最大值。如果所有子串对应的数都为正整数且这些数恰好覆盖了从 $1$ 到 $m$ 的所有正整数，则这组切割被称为一个有效的切割集。 例如，假设 PokeBlock 序列为 $101101001110$，我们做了 $5$ 次切割，如下： $10\ |\ 11\ |\ 010\ |\ 01\ |\ 1\ |\ 10$ 从而得到 $4$ 个二进制子串：$11$、$010$、$01$ 和 $1$，即对应 $3$、$2$、$1$ 和 $1$。此时 $m=3$，因为它们中最大值为 $3$，并且所有得到的数字都是正整数，且正好包含了 $1$ 到 $3$ 的所有数。因此，这组切割是一个有效的 $5$ 次切割集。 类型为 $k$ 的宝可梦要进化，只有在对 PokeBlock 进行了某种有效的 $k$ 次切割的情况下才会实现。相同大小的有效切割集可能有多种。若在某一组切割中有一个切割点在另一组中不存在，则认为二者为不同的切割集。 用 $f(k)$ 表示有效的 $k$ 次切割集数量。请计算 $s=f(2)+f(3)+\cdots+f(n+1)$ 的值。由于 $s$ 可能很大，请输出 $s$ 模 $10^9+7$ 的结果。

输入包含两行。第一行一个整数 $n$（$1 \leq n \leq 75$），表示 PokeBlock 的长度。第二行是长度为 $n$ 的 PokeBlock，一个仅包含 $0$ 和 $1$ 的二进制字符串。

输出一个整数，表示 $s$ 的值（即所有 $k$ 次有效切割集的数量之和），对 $10^9+7$ 取模。

在第一个样例中，有效切割集如下： 大小为 $2$：|1|011, 1|01|1, 10|1|1, 101|1|。 大小为 $3$：|1|01|1, |10|1|1, 10|1|1|, 1|01|1|。 大小为 $4$：|10|1|1|, |1|01|1|。 因此，$f(2)=4$，$f(3)=4$，$f(4)=2$。故 $s=10$。 在第二个样例中，有效切割集为： 大小为 $2$：|1|0。 故 $f(2)=1$，$f(3)=0$，所以 $s=1$。 由 ChatGPT 5 翻译