Random Elections

## 题目描述 总统选举将于明年在Bearland举行！每个人都为此感到非常兴奋！ 到目前为止，有三位候选人，A，B和C。 Bearland有n个公民。选举结果将对Bearland所有公民的生活产生很大的影响。由于这一重大责任，每个公民都会随机选择A，B和C之间的六个优先顺序（ABC,ACB,BCA,BAC,CBA,CAB）中的一个。如果该顺序为ABC，表示该选民最支持A，其次是B，最不支持C。 考虑到选民的偏好，Bearland政府已经设计了一个用来确定选举结果的函数$f$。 更具体地说，这个函数需要输入一个长度为$2^n$的01串$x$，并返回一个bool。数据保证$f$满足 $f(1-x_1,1-x_2,\ldots,1-x_n)=1-f(x_1,x_2,\ldots,x_n)$ 政府将进行3次比赛：A和B、B和C、C和A 在每一次比赛中（假设是候选人A和B之间的），如果第i个人更支持A，则$x_{i}=1$，否则$x_{i}=0$。假设函数f返回的值是1，则A胜，否则B胜 定义$p$为有一个候选人赢了两场的概率，你需要输出$p\times6^n$模1e9+7的值 ## 输入输出格式 ##### **输入格式：** 第一行输入一个整数n，表示共有$n$个选民（$1\le n\le20$） 第二行输入一个长度为$2^n$的01串。它的第i位表示f(i)的值。例如当第45（101101）位为1时，$f(1,0,1,1,0,1)=1$。 ##### 输出格式： 在第一行输出一个整数：$p\times6^n$模1e9+7的值

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 $ 10^{9}+7=1\ 000\ 000\ 007 $ .

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 one integer — answer to the problem.

3
01010101

216

3
01101001

168

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·6^{3}=216 $ .