English · Original
Chinese · Translation
Formal · Original
The presidential election is coming in Bearland next year! Everybody is so excited about this!
So far, there are three candidates, Alice, Bob, and Charlie.
There 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.
The 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_).
Three 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.
Define 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.
## Input
The first line contains one integer _n_ (1 ≤ _n_ ≤ 20).
The 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_)).
It 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_.
## Output
Output one integer — answer to the problem.
[samples]
## Note
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.
明年，熊国将举行总统选举！所有人都对此充满期待！
目前，有三位候选人：爱丽丝、鲍勃和查理。
熊国共有 #cf_span[n] 名公民。选举结果将决定熊国所有公民未来多年的生活。由于这一重大责任，每位 #cf_span[n] 名公民将独立且均匀随机地从爱丽丝、鲍勃和查理之间的六种偏好顺序中选择一种。
熊国政府设计了一个函数，用于根据选民的偏好确定选举结果。更具体地说，该函数是 （接受 #cf_span[n] 个布尔数并返回一个布尔数）。该函数还满足以下性质：#cf_span[f(1 - x1, 1 - x2, ..., 1 - xn) = 1 - f(x1, x2, ..., xn)]。
将进行三轮投票，每轮对应一对候选人：爱丽丝 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]，则第二位候选人赢得该轮。
定义存在一位候选人赢得两轮的概率为 #cf_span[p]。#cf_span[p·6n] 总是一个整数。请输出该整数对 #cf_span[109 + 7 = 1 000 000 007] 取模的值。
第一行包含一个整数 #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)]。
输出一个整数——问题的答案。
在第一个样例中，结果完全由第一位选民决定。换句话说，#cf_span[f(x1, x2, x3) = x1]。因此，无论发生什么，总会有一位候选人赢得两轮（更具体地说，是第一位选民偏好列表中排名第一的候选人），所以 #cf_span[p = 1]，我们输出 #cf_span[1·63 = 216]。
## Input
第一行包含一个整数 #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)]。
## Output
输出一个整数——问题的答案。
[samples]
## Note
在第一个样例中，结果完全由第一位选民决定。换句话说，#cf_span[f(x1, x2, x3) = x1]。因此，无论发生什么，总会有一位候选人赢得两轮（更具体地说，是第一位选民偏好列表中排名第一的候选人），所以 #cf_span[p = 1]，我们输出 #cf_span[1·63 = 216]。
Let $ n \in \mathbb{N} $, $ 1 \leq n \leq 20 $.
Let $ f: \{0,1\}^n \to \{0,1\} $ be a Boolean function satisfying the antisymmetry property:
$$
f(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.
$$
Let $ \mathcal{P} $ be the set of all strict total orders over the three candidates $ \{A, B, C\} $.
We have $ |\mathcal{P}| = 6 $. Each voter independently and uniformly selects an order from $ \mathcal{P} $.
For 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 $,
$$
x_i^{(XY)} =
\begin{cases}
1 & \text{if voter } i \text{ prefers } X \text{ to } Y, \\
0 & \text{otherwise}.
\end{cases}
$$
Let $ y^{(XY)} = f(\vec{x}^{(XY)}) $.
Then, the winner of the round $ (X,Y) $ is:
- $ X $ if $ y^{(XY)} = 1 $,
- $ Y $ if $ y^{(XY)} = 0 $.
Define the event $ E $: there exists a candidate who wins **two** out of the three pairwise rounds.
Let $ p = \Pr[E] $.
We are to compute $ p \cdot 6^n \mod (10^9 + 7) $.
The 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 $.
---
**Objective:** Compute $ p \cdot 6^n \mod 1000000007 $.
API Response (JSON)
{
"problem": {
"name": "E. Random Elections",
"description": {
"content": "The presidential election is coming in Bearland next year! Everybody is so excited about this! So far, there are three candidates, Alice, Bob, and Charlie. There are _n_ citizens in Bearland. The el",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 1048576
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF850E"
},
"statements": [
{
"statement_type": "Markdown",
"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 el...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "明年，熊国将举行总统选举！所有人都对此充满期待！\n\n目前，有三位候选人：爱丽丝、鲍勃和查理。\n\n熊国共有 #cf_span[n] 名公民。选举结果将决定熊国所有公民未来多年的生活。由于这一重大责任，每位 #cf_span[n] 名公民将独立且均匀随机地从爱丽丝、鲍勃和查理之间的六种偏好顺序中选择一种。\n\n熊国政府设计了一个函数，用于根据选民的偏好确定选举结果。更具体地说，该函数是 （接受 #cf...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "Formal"
}
]
}