Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

brute force

divide and conquer

fft

math

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Random Elections

time limit per test

2 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputThe 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.

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.

Examples

Input

3

01010101

Output

216

Input

3

01101001

Output

168

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 05:09:29 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|