Random Elections
Contest: Codeforces Round 432 (Div. 1, based on IndiaHacks Final Round 2017)
Difficulty rating: 2800
Tags: bitmasks, brute force, divide and conquer, fft, math

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 $$f(x_{1},x_{2},\ldots,x_{n}):\{0,1\}^{n}\to\{0,1\}$$ (takes n boolean numbers and returns a boolean number). The function also obeys the following property: f(1 - x1, 1 - x2, ..., 1 - xn) = 1 - f(x1, x2, ..., xn).

Three rounds will be run between each pair of candidates: Alice and Bob, Bob and Charlie, Charlie and Alice. In each round, xi 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(x1, x2, ..., xn) 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·6n is always an integer. Print the value of this integer modulo 109 + 7 = 1 000 000 007.

Input format:
The first line contains one integer n (1 ≤ n ≤ 20).

The next line contains a string of length 2n of zeros and ones, representing function f. Let bk(x) the k-th bit in binary representation of x, i-th (0-based) digit of this string shows the return value of f(b1(i), b2(i), ..., bn(i)).

It is guaranteed that f(1 - x1, 1 - x2, ..., 1 - xn) = 1 - f(x1, x2, ..., xn) for any values of x1, x2, ldots, xn.

Output format:
Output one integer — answer to the problem.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
In first sample, result is always fully determined by the first voter. In other words, f(x1, x2, x3) = x1. 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.

Example input:
3
01010101

Example output:
216

Example input:
3
01101001

Example output:
168

Editorial:
bk(x) denotes i-th bit of x. $$\operatorname{pop}(x)$$ denotes number of bits in x.
Count number of ways where Alice wins. Suppose Alice wins in first round with mask x and in third round with mask y (so, bi(x) = 1 or bi(y) = 1 if i voter preferred Alice in corresponding round). Necessary condition is f(x) = f(y) = 1.
Assume we fixed x and y. In how many ways we can choose orders for voters? If bi(x) = bi(y), we can chose two valid permutations for i-th voter. If $$b_{i}(x) \neq b_{i}(y)$$, only one permutation. So, total number of permutation is $$2^{n-\mathrm{pop}(x\oplus y)}$$.
So, answer to the problem is
Denote S = {x|f(x) = 1}. Lets solve more general problem, for each z, how many pairs (x, y) are there such that $$z = x \oplus y$$ and $$x,y \in S$$? This is well-known problem. There are multiple O(2nn) solutions. Probably first usage of this problem in competitive programming can be found here https://apps.topcoder.com/wiki/display/tc/SRM+518.
If you interesting in understanding this approach more deeply from math perspective, you can start investigate from here https://en.wikipedia.org/wiki/Fourier_transform_on_finite_groups.
Sorry for late editorial.
Btw, in task D there are always an answer (for any set S), that's called Reid's conjectue and was proven by T.X. Yao in 1988 (and have very difficult proof that I didn't manage to find in English; if somebody succeed in search, please direct it to me).