体育馆的领导们对费莉西蒂营地发生的变化着迷。所以,他们很想知道神奇宝贝进化背后的秘密。
训练营的组织者给了道馆领导一个 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。