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>
using namespace std;
template <class T>
void debug(T a, T b) {
  ;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
namespace std {
template <class S, class T>
ostream& operator<<(ostream& out, const pair<S, T>& a) {
  out << '(' << a.first << ',' << a.second << ')';
  return out;
}
}  // namespace std
template <long long int mod>
struct Int_ {
  unsigned x;
  unsigned mpow(Int_ a, unsigned k) {
    Int_ res = 1;
    while (k) {
      if (k & 1) res = res * a;
      a = a * a;
      k >>= 1;
    }
    return res.x;
  }
  unsigned inverse(Int_ a) { return mpow(a, mod - 2); }
  Int_() : x(0) {}
  Int_(long long sig) {
    int sigt = sig % mod;
    if (sigt < 0) sigt += mod;
    x = sigt;
  }
  unsigned get() const { return (unsigned)x; }
  Int_& operator+=(Int_ that) {
    if ((x += that.x) >= mod) x -= mod;
    return *this;
  }
  Int_& operator-=(Int_ that) {
    if ((x += mod - that.x) >= mod) x -= mod;
    return *this;
  }
  Int_& operator*=(Int_ that) {
    x = (unsigned long long)x * that.x % mod;
    return *this;
  }
  Int_& operator=(Int_ that) {
    x = that.x;
    return *this;
  }
  Int_& operator/=(Int_ that) {
    x = (unsigned long long)x * inverse(that.x) % mod;
    return *this;
  }
  bool operator==(Int_ that) const { return x == that.x; }
  bool operator!=(Int_ that) const { return x != that.x; }
  Int_ operator-() const { return Int_(0) - Int_(*this); }
  Int_ operator+(Int_ that) const { return Int_(*this) += that; }
  Int_ operator-(Int_ that) const { return Int_(*this) -= that; }
  Int_ operator*(Int_ that) const { return Int_(*this) *= that; }
  Int_ operator/(Int_ that) const { return Int_(*this) /= that; }
  Int_ inv() { return Int_(mpow(x, mod - 2)); }
};
namespace std {
template <long long int mod>
ostream& operator<<(ostream& out, const Int_<mod>& a) {
  out << a.get();
  return out;
}
template <long long int mod>
istream& operator>>(istream& in, Int_<mod>& a) {
  in >> a.x;
  return in;
}
};  // namespace std
Int_<1000000007> mpow(Int_<1000000007> a, long long int k) {
  Int_<1000000007> res = 1;
  while (k) {
    if (k & 1) res = res * a;
    a = a * a;
    k >>= 1;
  }
  return res;
}
const int mod = 1000000007;
const long long int DIV2 = 500000004;
void chadd(int& x, int b) {
  x += b;
  if (x >= mod) x -= mod;
}
void conv(const vector<int>& A, const vector<int>& B, vector<int>& C) {
  int n = A.size();
  C.clear();
  C.resize(n);
  if (n == 1) {
    C[0] = A[0] * (long long int)B[0] % mod;
  } else {
    vector<int> S1(n / 2), S2(n / 2), D1(n / 2), D2(n / 2);
    for (int i = 0; i < (n / 2); ++i) {
      S1[i] = D1[i] = A[i];
      S2[i] = D2[i] = B[i];
      chadd(S1[i], A[i + n / 2]);
      chadd(D1[i], mod - A[i + n / 2]);
      chadd(S2[i], B[i + n / 2]);
      chadd(D2[i], mod - B[i + n / 2]);
    }
    vector<int> RS, RD;
    conv(S1, S2, RS);
    conv(D1, D2, RD);
    for (int i = 0; i < (n / 2); ++i) {
      C[i] = (RS[i] + RD[i]) * DIV2 % mod;
      C[i + n / 2] = (RS[i] + mod - RD[i]) * DIV2 % mod;
    }
  }
}
int n, N;
char s[1100000];
Int_<1000000007> pw[30];
int main() {
  cin >> n;
  N = (1 << n);
  scanf("%s", s);
  pw[0] = 1;
  for (int i = 0; i < (25); ++i) pw[i + 1] = pw[i] * 2;
  vector<int> A(N), cv(N);
  for (int i = 0; i < (N); ++i) A[i] = s[i] - '0';
  conv(A, A, cv);
  Int_<1000000007> res = 0;
  for (int i = 0; i < (N); ++i) {
    res += pw[n - __builtin_popcount(i)] * cv[i];
  }
  cout << res * 3 << endl;
  return 0;
}
