{"raw_statement":[{"iden":"statement","content":"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.\n\nThe 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.\n\nSuppose 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.\n\nThe _n_ + 1 choices of making cuts are as follows (where a _|_ denotes a possible cut):\n\n<center>| _b_0 | _b_1 | _b_2 | ... | _b__n_ - 2 | _b__n_ - 1 |</center>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.\n\nFor example, suppose the given PokeBlock sequence is 101101001110 and we made 5 cuts in the following way:\n\n<center>10 | 11 | 010 | 01 | 1 | 10</center>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.\n\nA 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.\n\nLet _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."},{"iden":"input","content":"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_."},{"iden":"output","content":"Output a single integer, containing the answer to the problem, i.e., the value of _s_ modulo 109 + 7."},{"iden":"examples","content":"Input\n\n4\n1011\n\nOutput\n\n10\n\nInput\n\n2\n10\n\nOutput\n\n1"},{"iden":"note","content":"In the first sample, the sets of valid cuts are:\n\nSize 2: _|1|011_, _1|01|1_, _10|1|1_, _101|1|_.\n\nSize 3: _|1|01|1_, _|10|1|1_, _10|1|1|_, _1|01|1|_.\n\nSize 4: _|10|1|1|_, _|1|01|1|_.\n\nHence, _f_(2) = 4, _f_(3) = 4 and _f_(4) = 2. So, the value of _s_ = 10.\n\nIn the second sample, the set of valid cuts is:\n\nSize 2: |1|0.\n\nHence, _f_(2) = 1 and _f_(3) = 0. So, the value of _s_ = 1."}],"translated_statement":[{"iden":"statement","content":"健身领袖们对Felicity营地中发生的宝可梦进化现象感到着迷，因此他们好奇进化背后的秘密。\n\n营地组织者给了健身领袖们一个PokeBlock，这是一个由 #cf_span[n] 个成分组成的序列。每个成分可以是类型 #cf_span[0] 或 #cf_span[1]。组织者告诉健身领袖们，要进化一个类型为 #cf_span[k]（#cf_span[k ≥ 2]）的宝可梦，他们需要在PokeBlock上进行一组有效的 #cf_span[k] 次切割，以获得更小的块。\n\n假设给定的PokeBlock序列为 #cf_span[b0b1b2... bn - 1]。你可以在 #cf_span[n + 1] 个位置选择切割，即：在 #cf_span[b0] 之前、在 #cf_span[b0] 和 #cf_span[b1] 之间、在 #cf_span[b1] 和 #cf_span[b2] 之间、...、在 #cf_span[bn - 2] 和 #cf_span[bn - 1] 之间，以及在 #cf_span[bn - 1] 之后。\n\n这 #cf_span[n + 1] 个切割位置如下所示（其中 _|_ 表示一个可能的切割点）：\n\n考虑一组 #cf_span[k] 次切割。每一对相邻的切割之间会形成一个二进制字符串，由其中的成分类型构成。第一个切割之前的成分和最后一个切割之后的成分会被浪费，即不被考虑。因此，恰好会有 #cf_span[k - 1] 个这样的二进制子串。每个子串都可以被解读为一个二进制数。设 #cf_span[m] 为这些数中的最大值。如果所有得到的数都是正数，并且得到的数的集合包含从 #cf_span[1] 到 #cf_span[m] 的所有整数，则称这组切割为一个有效的切割集。\n\n例如，假设给定的PokeBlock序列为 #cf_span[101101001110]，我们进行了 #cf_span[5] 次切割，方式如下：\n\n于是得到的 #cf_span[4] 个二进制子串为：#cf_span[11]、#cf_span[010]、#cf_span[01] 和 #cf_span[1]，分别对应数字 #cf_span[3]、#cf_span[2]、#cf_span[1] 和 #cf_span[1]。这里 #cf_span[m = 3]，因为它是所得数字中的最大值。所有得到的数都是正数，并且我们得到了从 #cf_span[1] 到 #cf_span[m] 的所有整数。因此，这组切割是一个有效的 #cf_span[5] 次切割集。\n\n只有当使用一组有效的 #cf_span[k] 次切割时，类型为 #cf_span[k] 的宝可梦才会进化。可能存在许多相同大小的有效切割集。两个大小为 #cf_span[k] 的有效切割集被认为是不同的，当且仅当其中一个集合中存在另一个集合中没有的切割。\n\n设 #cf_span[f(k)] 表示有效的 #cf_span[k] 次切割集的数量。求 #cf_span[s = f(2) + f(3) + ... + f(n + 1)] 的值。由于 #cf_span[s] 的值可能非常大，请输出 #cf_span[s] 对 #cf_span[109 + 7] 取模的结果。\n\n输入包含两行。第一行是一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 75]）——PokeBlock的长度。第二行包含一个长度为 #cf_span[n] 的二进制字符串，即PokeBlock。\n\n输出一个整数，即该问题的答案，即 #cf_span[s] 对 #cf_span[109 + 7] 取模的结果。\n\n在第一个样例中，有效的切割集如下：\n\n大小为 #cf_span[2]：_|1|011_、_1|01|1_、_10|1|1_、_101|1|_。\n\n大小为 #cf_span[3]：_|1|01|1_、_|10|1|1_、_10|1|1|_、_1|01|1|_。\n\n大小为 #cf_span[4]：_|10|1|1|_、_|1|01|1|_。\n\n因此，#cf_span[f(2) = 4]、#cf_span[f(3) = 4] 且 #cf_span[f(4) = 2]。所以 #cf_span[s = 10]。\n\n在第二个样例中，有效的切割集为：\n\n大小为 #cf_span[2]：|1|0。\n\n因此，#cf_span[f(2) = 1] 且 #cf_span[f(3) = 0]。所以 #cf_span[s = 1]。"},{"iden":"input","content":"输入包含两行。第一行是一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 75]）——PokeBlock的长度。第二行包含一个长度为 #cf_span[n] 的二进制字符串，即PokeBlock。"},{"iden":"output","content":"输出一个整数，即该问题的答案，即 #cf_span[s] 对 #cf_span[109 + 7] 取模的结果。"},{"iden":"examples","content":"输入\n4\n1011\n输出\n10\n输入\n2\n10\n输出\n1"},{"iden":"note","content":"在第一个样例中，有效的切割集如下：\n大小为 #cf_span[2]：_|1|011_、_1|01|1_、_10|1|1_、_101|1|_。\n大小为 #cf_span[3]：_|1|01|1_、_|10|1|1_、_10|1|1|_、_1|01|1|_。\n大小为 #cf_span[4]：_|10|1|1|_、_|1|01|1|_。\n因此，#cf_span[f(2) = 4]、#cf_span[f(3) = 4] 且 #cf_span[f(4) = 2]。所以 #cf_span[s = 10]。\n在第二个样例中，有效的切割集为：\n大小为 #cf_span[2]：|1|0。\n因此，#cf_span[f(2) = 1] 且 #cf_span[f(3) = 0]。所以 #cf_span[s = 1]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of a binary string $ s = s_0 s_1 \\dots s_{n-1} $, where $ s_i \\in \\{0,1\\} $.  \nLet $ C = \\{c_0, c_1, \\dots, c_n\\} $ be the set of $ n+1 $ possible cut positions: before $ s_0 $, between each adjacent pair, and after $ s_{n-1} $.  \n\nFor a set of $ k $ cuts $ \\{c_{i_0}, c_{i_1}, \\dots, c_{i_{k-1}}\\} $ with $ 0 \\le i_0 < i_1 < \\dots < i_{k-1} \\le n $, define the $ k-1 $ contiguous substrings between consecutive cuts:  \n$ b_j = s[i_j : i_{j+1}] $ for $ j = 0, 1, \\dots, k-2 $, each interpreted as a binary number (ignoring leading zeros).  \n\n**Constraints**  \n1. $ 1 \\le n \\le 75 $  \n2. Each substring $ b_j $ must represent a **positive** integer (i.e., cannot be \"0\").  \n3. Let $ m = \\max \\{ \\text{int}(b_j) \\mid j = 0, \\dots, k-2 \\} $.  \n4. The set $ \\{ \\text{int}(b_j) \\mid j = 0, \\dots, k-2 \\} $ must equal $ \\{1, 2, \\dots, m\\} $ (i.e., contains all integers from 1 to $ m $ without gaps).  \n\n**Objective**  \nDefine $ f(k) $ as the number of valid sets of $ k $ cuts satisfying the above conditions.  \nCompute:  \n$$\ns = \\sum_{k=2}^{n+1} f(k) \\mod (10^9 + 7)\n$$","simple_statement":null,"has_page_source":false}