CF757D.Felicity's Big Secret Revealed

The gym leaders were fascinated by the evolutions which took place at Felicity camp. So, they were curious to know about the secret behind evolving Pokemon.

The organizers of the camp gave the gym leaders a PokeBlock, a sequence of n ingredients. Each ingredient can be of type 0 or 1. Now the organizers told the gym leaders that to evolve a Pokemon of type k (k ≥ 2), they need to make a valid set of k cuts on the PokeBlock to get smaller blocks.

Suppose the given PokeBlock sequence is _b_0_b_1_b_2... b__n - 1. You have a choice of making cuts at n + 1 places, i.e., Before _b_0, between _b_0 and _b_1, between _b_1 and _b_2, ..., between b__n - 2 and b__n - 1, and after b__n - 1.

The n + 1 choices of making cuts are as follows (where a | denotes a possible cut):

| _b_0 | _b_1 | _b_2 | ... | b__n - 2 | b__n - 1 |

Consider a sequence of k cuts. Now each pair of consecutive cuts will contain a binary string between them, formed from the ingredient types. The ingredients before the first cut and after the last cut are wasted, which is to say they are not considered. So there will be exactly k - 1 such binary substrings. Every substring can be read as a binary number. Let m be the maximum number out of the obtained numbers. If all the obtained numbers are positive and the set of the obtained numbers contains all integers from 1 to m, then this set of cuts is said to be a valid set of cuts.

For example, suppose the given PokeBlock sequence is 101101001110 and we made 5 cuts in the following way:

10 | 11 | 010 | 01 | 1 | 10

So the 4 binary substrings obtained are: 11, 010, 01 and 1, which correspond to the numbers 3, 2, 1 and 1 respectively. Here m = 3, as it is the maximum value among the obtained numbers. And all the obtained numbers are positive and we have obtained all integers from 1 to m. Hence this set of cuts is a valid set of 5 cuts.

A Pokemon of type k will evolve only if the PokeBlock is cut using a valid set of k cuts. There can be many valid sets of the same size. Two valid sets of k cuts are considered different if there is a cut in one set which is not there in the other set.

Let f(k) denote the number of valid sets of k cuts. Find the value of . Since the value of s can be very large, output s modulo 109 + 7.

道馆馆主们对菲利西蒂营地中发生的宝可梦进化现象十分着迷，因此他们迫切想要了解宝可梦进化的秘密。

营地组织者向道馆馆主们提供了一块“宝可梦方块”（PokeBlock），它是一段由 $ n $ 个原料组成的序列。每个原料的类型为 0 或 1。接着，组织者告诉馆主们：若要使一只类型为 $ k $（$ k \geq 2 $）的宝可梦进化，就必须在该宝可梦方块上进行一组有效的 $ k $ 处切割，从而得到若干更小的方块。

设给定的宝可梦方块序列为 $ b_0b_1b_2\ldots 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 $ | ... | $ b_{n-2} $ | $ b_{n-1} $ |

考虑一组共 $ k $ 处切割。每一对相邻切割之间会形成一个二进制字符串（由其间原料类型构成）。位于第一处切割之前和最后一处切割之后的原料将被废弃，即不参与后续计算。因此，恰好会产生 $ k-1 $ 个这样的二进制子串。每个子串均可被视作一个二进制数。令 $ m $ 为所有所得数值中的最大值。若所有所得数值均为正整数，且所得数值的集合恰好包含从 1 到 $ m $ 的全部整数，则称这组 $ k $ 处切割为一组有效的切割。

例如，假设给定的宝可梦方块序列为 101101001110，我们按如下方式进行了 5 处切割：

10 | 11 | 010 | 01 | 1 | 10

由此得到的 4 个二进制子串为：11、010、01 和 1，它们对应的十进制数值分别为 3、2、1 和 1。此时 $ m = 3 $（即所得数值中的最大值），且所有所得数值均为正整数，并包含了从 1 到 $ m $ 的所有整数。因此，这组 5 处切割是有效的。

一只类型为 $ k $ 的宝可梦仅当宝可梦方块通过一组有效的 $ k $ 处切割被分割时，才能完成进化。对于同一尺寸 $ k $，可能存在多组不同的有效切割方案。若两组 $ k $ 处切割中存在某一处切割位置仅属于其中一组，则认为这两组切割方案不同。

令 $ f(k) $ 表示大小为 $ k $ 的有效切割方案的总数。请计算

的值。由于 $ s $ 的值可能非常大，请输出 $ s \bmod (10^9 + 7) $。

The input consists of two lines. The first line consists an integer n (1 ≤ n ≤ 75) — the length of the PokeBlock. The next line contains the PokeBlock, a binary string of length n.

输入包含两行。第一行包含一个整数 $n$（$1 \leq n \leq 75$）—— PokeBlock 的长度。下一行包含该 PokeBlock，即一个长度为 $n$ 的二进制字符串。

Output a single integer, containing the answer to the problem, i.e., the value of s modulo 109 + 7.

输出一个整数，表示该问题的答案，即 $ s $ 对 $ 10^9 + 7 $ 取模的值。

In the first sample, the sets of valid cuts are:

Size 2: |1|011, 1|01|1, 10|1|1, 101|1|.

Size 3: |1|01|1, |10|1|1, 10|1|1|, 1|01|1|.

Size 4: |10|1|1|, |1|01|1|.

Hence, f(2) = 4, f(3) = 4 and f(4) = 2. So, the value of s = 10.

In the second sample, the set of valid cuts is:

Size 2: |1|0.

Hence, f(2) = 1 and f(3) = 0. So, the value of s = 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 $。