CF850E.Random Elections

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.

明年，熊国将迎来总统大选！所有人都对此激动不已！

目前，共有三位候选人：爱丽丝（Alice）、鲍勃（Bob）和查理（Charlie）。

熊国共有 $ n $ 位公民。此次选举结果将决定熊国全体公民未来多年的命运。正因肩负如此重大的责任，每位公民将独立地、均匀随机地从爱丽丝、鲍勃与查理三者之间选择一种偏好排序（共 $ 3! = 6 $ 种可能），作为自己的投票偏好。

熊国政府设计了一个函数，用于根据所有选民的偏好确定最终选举结果。具体而言，该函数为

（输入为 $ n $ 个布尔值，输出为一个布尔值）。该函数还满足如下性质：

$$f(1 - x_1,\, 1 - x_2,\, \dots,\, 1 - x_n) = 1 - f(x_1,\, x_2,\, \dots,\, x_n).$$

接下来将举行三轮两两对决：爱丽丝 vs 鲍勃、鲍勃 vs 查理、查理 vs 爱丽丝。在每一轮中，对第 $ i $ 位公民，若其在本轮所比较的两位候选人中更偏好第一位候选人，则令 $ x_i = 1 $；否则令 $ x_i = 0 $。随后计算 $ y = f(x_1,, x_2,, \dots,, x_n) $。若 $ y = 1 $，则宣布本轮中第一位候选人为胜者；若 $ y = 0 $，则第二位候选人为胜者。

定义事件“存在一位候选人在三轮中赢得其中两轮”的概率为 $ p $。可以证明：$ p \cdot 6^n $ 恒为整数。请输出该整数对 $ 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.

第一行包含一个整数 $n$（$1 \leq n \leq 20$）。

下一行包含一个长度为 $2^n$ 的由 0 和 1 组成的字符串，表示函数 $f$。令 $b_k(x)$ 表示 $x$ 的二进制表示中第 $k$ 位（从高位还是低位起始？此处按常规理解为：$b_1(i), b_2(i), \dots, b_n(i)$ 构成 $i$ 的 $n$ 位二进制表示，高位补零），该字符串中第 $i$ 位（从 0 开始计数）表示 $f(b_1(i),\, b_2(i),\, \dots,\, b_n(i))$ 的返回值。

保证对任意 $x_1, x_2, \dots, x_n$，均有

$$f(1 - x_1,\, 1 - x_2,\, \dots,\, 1 - x_n) = 1 - f(x_1,\, x_2,\, \dots,\, x_n).$$

Output one integer — answer to the problem.

输出一个整数——问题的答案。

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.

在第一个样例中，结果总是完全由第一位投票者决定。换句话说，$ f(x_1,,x_2,,x_3) = x_1 $。因此，无论发生什么情况，总有一位候选人赢得两轮（更具体地说，是第一位投票者偏好列表中排在首位的候选人），故 $ p = 1 $，我们输出 $ 1 \cdot 6^3 = 216 $。