← 返回题目列表

Codeforces · 757/D

D. 费莉西蒂的大秘密揭晓

中文机器翻译题面 查看原题

体育馆的领导们对费莉西蒂营地发生的变化着迷。所以,他们很想知道神奇宝贝进化背后的秘密。

训练营的组织者给了道馆领导一个 PokeBlock,一个由 n 个成分组成的序列。每种成分都可以是 0 型或 1 型。现在,组织者告诉健身房领导者,要进化出 k 型(k ≥ 2)的 Pokemon,他们需要在 PokeBlock 上进行一组有效的 k 次切割以获得更小的块。

假设给定的 PokeBlock 序列是 b0b1b2... bn - 1。您可以选择在 n + 1 个位置进行切割,即 b0 之前、b0 和 b1 之间、b1 和 b2 之间、...、bn - 2 和 bn - 1 之间以及 bn - 1 之后。

进行切割的 n + 1 种选择如下(其中 | 表示可能的切割):

| b0 | b1 | b2 | ... | bn - 2 | bn - 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,因为它是获得的数字中的最大值。并且所有得到的数字都是正数,我们得到了从1到m的所有整数。因此,这组切割是一组有效的 5 次切割。

仅当使用有效的 k 组切割来切割 PokeBlock 时,k 类型的 Pokemon 才会进化。可以有许多相同大小的有效集。如果一组中存在一个切割而另一组中不存在,则两个有效的 k 个切割集合被认为是不同的。

设 f(k) 表示 k 次切割的有效组数。求 $$s = \sum_{k=2}^{n+1} f(k)$$ 的值。由于 s 的值可能非常大,因此输出 s 对 109 + 7 求模。

输入

输入由两行组成。第一行包含一个整数 n (1 ≤ n ≤ 75)——PokeBlock 的长度。下一行包含 PokeBlock,一个长度为 n 的二进制字符串。

输出

输出一个整数,包含问题的答案,即 s 模 109 + 7 的值。

示例

输入 #1

4
1011

输出 #1

10

输入 #2

2
10

输出 #2

1

注意

在第一个示例中,有效割集是:

尺寸 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。