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