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.
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.
In first sample, result is always fully determined by the first voter. In other words, *f*(*x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, *x*<sub class="lower-index">3</sub>) = *x*<sub class="lower-index">1</sub>. 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<sup class="upper-index">3</sup> = 216.