{"raw_statement":[{"iden":"statement","content":"The presidential election is coming in Bearland next year! Everybody is so excited about this!\n\nSo far, there are three candidates, Alice, Bob, and Charlie.\n\nThere are _n_ citizens in Bearland. The election result will determine the life of all citizens of Bearland for many years. Because of this great responsibility, each of _n_ citizens will choose one of six orders of preference between Alice, Bob and Charlie uniformly at random, independently from other voters.\n\nThe government of Bearland has devised a function to help determine the outcome of the election given the voters preferences. More specifically, the function is (takes _n_ boolean numbers and returns a boolean number). The function also obeys the following property: _f_(1 - _x_1, 1 - _x_2, ..., 1 - _x__n_) = 1 - _f_(_x_1, _x_2, ..., _x__n_).\n\nThree rounds will be run between each pair of candidates: Alice and Bob, Bob and Charlie, Charlie and Alice. In each round, _x__i_ will be equal to 1, if _i_\\-th citizen prefers the first candidate to second in this round, and 0 otherwise. After this, _y_ = _f_(_x_1, _x_2, ..., _x__n_) will be calculated. If _y_ = 1, the first candidate will be declared as winner in this round. If _y_ = 0, the second will be the winner, respectively.\n\nDefine the probability that there is a candidate who won two rounds as _p_. _p_·6_n_ is always an integer. Print the value of this integer modulo 109 + 7 = 1 000 000 007."},{"iden":"input","content":"The first line contains one integer _n_ (1 ≤ _n_ ≤ 20).\n\nThe next line contains a string of length 2_n_ of zeros and ones, representing function _f_. Let _b__k_(_x_) the _k_\\-th bit in binary representation of _x_, _i_\\-th (0-based) digit of this string shows the return value of _f_(_b_1(_i_), _b_2(_i_), ..., _b__n_(_i_)).\n\nIt is guaranteed that _f_(1 - _x_1, 1 - _x_2, ..., 1 - _x__n_) = 1 - _f_(_x_1, _x_2, ..., _x__n_) for any values of _x_1, _x_2, _ldots_, _x__n_."},{"iden":"output","content":"Output one integer — answer to the problem."},{"iden":"examples","content":"Input\n\n3\n01010101\n\nOutput\n\n216\n\nInput\n\n3\n01101001\n\nOutput\n\n168"},{"iden":"note","content":"In first sample, result is always fully determined by the first voter. In other words, _f_(_x_1, _x_2, _x_3) = _x_1. Thus, any no matter what happens, there will be a candidate who won two rounds (more specifically, the candidate who is at the top of voter 1's preference list), so _p_ = 1, and we print 1·63 = 216."}],"translated_statement":[{"iden":"statement","content":"明年，熊国将举行总统选举！所有人都对此充满期待！\n\n目前，有三位候选人：爱丽丝、鲍勃和查理。\n\n熊国共有 #cf_span[n] 名公民。选举结果将决定熊国所有公民未来多年的生活。由于这一重大责任，每位 #cf_span[n] 名公民将独立且均匀随机地从爱丽丝、鲍勃和查理之间的六种偏好顺序中选择一种。\n\n熊国政府设计了一个函数，用于根据选民的偏好确定选举结果。更具体地说，该函数是  （接受 #cf_span[n] 个布尔数并返回一个布尔数）。该函数还满足以下性质：#cf_span[f(1 - x1, 1 - x2, ..., 1 - xn) = 1 - f(x1, x2, ..., xn)]。\n\n将进行三轮投票，每轮对应一对候选人：爱丽丝 vs 鲍勃、鲍勃 vs 查理、查理 vs 爱丽丝。在每轮中，#cf_span[xi] 将等于 #cf_span[1]，如果第 #cf_span[i] 位公民在该轮中更偏好第一位候选人而非第二位；否则为 #cf_span[0]。随后计算 #cf_span[y = f(x1, x2, ..., xn)]。若 #cf_span[y = 1]，则第一位候选人赢得该轮；若 #cf_span[y = 0]，则第二位候选人赢得该轮。\n\n定义存在一位候选人赢得两轮的概率为 #cf_span[p]。#cf_span[p·6n] 总是一个整数。请输出该整数对 #cf_span[109 + 7 = 1 000 000 007] 取模的值。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 20]）。\n\n第二行包含一个长度为 #cf_span[2n] 的由 0 和 1 组成的字符串，表示函数 #cf_span[f]。令 #cf_span[bk(x)] 表示 #cf_span[x] 的二进制表示中的第 #cf_span[k] 位，该字符串的第 #cf_span[i] 个（从 0 开始）数字表示 #cf_span[f(b1(i), b2(i), ..., bn(i))] 的返回值。\n\n保证对于任意 #cf_span[x1, x2, ldots, xn]，均有 #cf_span[f(1 - x1, 1 - x2, ..., 1 - xn) = 1 - f(x1, x2, ..., xn)]。\n\n输出一个整数——问题的答案。\n\n在第一个样例中，结果完全由第一位选民决定。换句话说，#cf_span[f(x1, x2, x3) = x1]。因此，无论发生什么，总会有一位候选人赢得两轮（更具体地说，是第一位选民偏好列表中排名第一的候选人），所以 #cf_span[p = 1]，我们输出 #cf_span[1·63 = 216]。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 20]）。第二行包含一个长度为 #cf_span[2n] 的由 0 和 1 组成的字符串，表示函数 #cf_span[f]。令 #cf_span[bk(x)] 表示 #cf_span[x] 的二进制表示中的第 #cf_span[k] 位，该字符串的第 #cf_span[i] 个（从 0 开始）数字表示 #cf_span[f(b1(i), b2(i), ..., bn(i))] 的返回值。保证对于任意 #cf_span[x1, x2, ldots, xn]，均有 #cf_span[f(1 - x1, 1 - x2, ..., 1 - xn) = 1 - f(x1, x2, ..., xn)]。"},{"iden":"output","content":"输出一个整数——问题的答案。"},{"iden":"examples","content":"输入301010101输出216输入301101001输出168"},{"iden":"note","content":"在第一个样例中，结果完全由第一位选民决定。换句话说，#cf_span[f(x1, x2, x3) = x1]。因此，无论发生什么，总会有一位候选人赢得两轮（更具体地说，是第一位选民偏好列表中排名第一的候选人），所以 #cf_span[p = 1]，我们输出 #cf_span[1·63 = 216]。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 20 $.  \nLet $ f: \\{0,1\\}^n \\to \\{0,1\\} $ be a Boolean function satisfying the antisymmetry property:  \n$$\nf(1 - x_1, 1 - x_2, \\dots, 1 - x_n) = 1 - f(x_1, x_2, \\dots, x_n), \\quad \\forall (x_1, \\dots, x_n) \\in \\{0,1\\}^n.\n$$\n\nLet $ \\mathcal{P} $ be the set of all strict total orders over the three candidates $ \\{A, B, C\\} $.  \nWe have $ |\\mathcal{P}| = 6 $. Each voter independently and uniformly selects an order from $ \\mathcal{P} $.\n\nFor each pair of candidates $ (X,Y) \\in \\{(A,B), (B,C), (C,A)\\} $, define a vector $ \\vec{x}^{(XY)} \\in \\{0,1\\}^n $, where for voter $ i $,  \n$$\nx_i^{(XY)} = \n\\begin{cases}\n1 & \\text{if voter } i \\text{ prefers } X \\text{ to } Y, \\\\\n0 & \\text{otherwise}.\n\\end{cases}\n$$\n\nLet $ y^{(XY)} = f(\\vec{x}^{(XY)}) $.  \nThen, the winner of the round $ (X,Y) $ is:\n- $ X $ if $ y^{(XY)} = 1 $,\n- $ Y $ if $ y^{(XY)} = 0 $.\n\nDefine the event $ E $: there exists a candidate who wins **two** out of the three pairwise rounds.\n\nLet $ p = \\Pr[E] $.  \nWe are to compute $ p \\cdot 6^n \\mod (10^9 + 7) $.\n\nThe function $ f $ is given as a binary string of length $ 2^n $: the $ i $-th bit (0-based) is $ f(b_1(i), b_2(i), \\dots, b_n(i)) $, where $ b_k(i) $ is the $ k $-th bit in the $ n $-bit binary representation of $ i $.\n\n---\n\n**Objective:** Compute $ p \\cdot 6^n \\mod 1000000007 $.","simple_statement":null,"has_page_source":false}