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 <image> (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

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

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(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.
#include <bits/stdc++.h>
template <class T>
T Min(const T &a, const T &b) {
  return a < b ? a : b;
}
template <class T>
T Max(const T &a, const T &b) {
  return a > b ? a : b;
}
template <class T>
bool Chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool Chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
class fast_input {
 private:
  static const int SIZE = 1 << 15 | 1;
  char buf[SIZE], *front, *back;
  void Next(char &c) {
    if (front == back) back = (front = buf) + fread(buf, 1, SIZE, stdin);
    c = front == back ? (char)EOF : *front++;
  }

 public:
  template <class T>
  void operator()(T &x) {
    char c, f = 1;
    for (Next(c); c > '9' || c < '0'; Next(c))
      if (c == '-') f = -1;
    for (x = 0; c >= '0' && c <= '9'; Next(c)) x = x * 10 + c - '0';
    x *= f;
  }
  void operator()(char &c, char l = 'a', char r = 'z') {
    for (Next(c); c > r || c < l; Next(c))
      ;
  }
} input;
const int SN = 20 + 1;
const int SX = 1 << 20 | 1;
const int MOD = 1000000007;
int a[SX], bit[SX];
void FWT(int *, int);
int F(int);
int DF(int);
int main() {
  char c;
  int x, y, z, n;
  input(n);
  for (int i = (0), i_end = (1 << n); i < i_end; ++i)
    input(c, '0', '1'), a[i] = c - '0';
  FWT(a, n);
  for (int i = (0), i_end = (1 << n); i < i_end; ++i)
    a[i] = 1LL * a[i] * a[i] % MOD;
  FWT(a, n);
  x = MOD + 1 >> 1, y = 1;
  for (int i = (1), i_end = (n); i <= i_end; ++i) y = 1LL * y * x % MOD;
  for (int i = (0), i_end = (1 << n); i < i_end; ++i)
    a[i] = 1LL * a[i] * y % MOD;
  for (int i = (1), i_end = (1 << n); i < i_end; ++i)
    bit[i] = bit[i >> 1] + (i & 1);
  x = 0;
  for (int i = (0), i_end = (1 << n); i < i_end; ++i)
    x = (x + (1LL << n - bit[i]) * a[i]) % MOD;
  printf("%d\n", int(3LL * x % MOD));
  return 0;
}
void FWT(int *x, int max_bit) {
  int p, q;
  for (int i = (0), i_end = (max_bit); i < i_end; ++i)
    for (int j = (0), j_end = (1 << max_bit); j < j_end; ++j)
      if (~j >> i & 1) {
        p = x[j], q = x[j + (1 << i)];
        x[j] = F(p + q), x[j + (1 << i)] = DF(p - q);
      }
}
int F(int x) { return x >= MOD ? x - MOD : x; }
int DF(int x) { return x < 0 ? x + MOD : x; }
