CF850E 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的值

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 $ .