Inspired by the tv series Stranger Things, bear Limak is going for a walk between two mirror worlds.

There are two perfect binary trees of height H, each with the standard numeration of vertices from 1 to 2^H-1. The root is 1 and the children of x are 2 \cdot x and 2 \cdot x + 1.

Let L denote the number of leaves in a single tree, L = 2^{H-1}.

You are given a permutation P_1, P_2, \ldots, P_L of numbers 1 through L. It describes L special edges that connect leaves of the two trees. There is a special edge between vertex L+i-1 in the first tree and vertex L+P_i-1 in the second tree.

graph for sample1

drawing for the first sample test, permutation P = (2, 3, 1, 4), special edges in green

Let's define product of a cycle as the product of numbers in its vertices. Compute the sum of products of all simple cycles that have exactly two special edges, modulo (10^9+7).

A simple cycle is a cycle of length at least 3, without repeated vertices or edges.

Constraints

* 2 \leq H \leq 18
* 1 \leq P_i \leq L where L = 2^{H-1}
* P_i \neq P_j (so this is a permutation)

Input

Input is given from Standard Input in the following format (where L = 2^{H-1}).


H
P_1 P_2 \cdots P_L


Output

Compute the sum of products of simple cycles that have exactly two special edges. Print the answer modulo (10^9+7).

Examples

Input

3
2 3 1 4


Output

121788


Input

2
1 2


Output

36


Input

5
6 14 15 7 12 16 5 4 11 9 3 10 8 2 13 1


Output

10199246
#pragma comment(linker, "/STACK:512000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
#ifdef AIM
#include <sys/resource.h>
#endif
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve(__attribute__((unused)) bool);
void precalc();
clock_t start;
#define FILENAME ""

int main() {
#ifdef AIM
  string s = FILENAME;
//    assert(!s.empty());
  freopen("/home/alexandero/ClionProjects/cryptozoology/input.txt", "r", stdin);
  //freopen("/home/alexandero/ClionProjects/cryptozoology/output.txt", "w", stdout);
#else
//    freopen(FILENAME ".in", "r", stdin);
//    freopen(FILENAME ".out", "w", stdout);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    start = clock();
    int t = 1;
#ifndef AIM
  cout.sync_with_stdio(0);
  cin.tie(0);
#endif

#ifdef AIM
  const rlim_t kStackSize = 256 * 1024 * 1024;
  struct rlimit rl;
  int result;

  result = getrlimit(RLIMIT_STACK, &rl);
  if (result == 0)
  {
    if (rl.rlim_cur < kStackSize)
    {
      rl.rlim_cur = kStackSize;
      result = setrlimit(RLIMIT_STACK, &rl);
      if (result != 0)
      {
        fprintf(stderr, "setrlimit returned result = %d\n", result);
      }
    }
  }
#endif

  precalc();
  cout.precision(10);
  cout << fixed;
  //cin >> t;
  int testNum = 1;
  while (t--) {
      //cout << "Case #" << testNum++ << ": ";
      solve(true);
  }
  cout.flush();
#ifdef AIM1
    while (true) {
      solve(false);
  }
#endif

#ifdef AIM
  cout.flush();
  auto end = clock();

  usleep(10000);
  print_stats(end - start);
  usleep(10000);
#endif

    return 0;
}

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}

template <typename T>
void make_unique(vector<T>& a) {
    sort(all(a));
    a.erase(unique(all(a)), a.end());
}

template<typename T>
void relax_min(T& cur, T val) {
    cur = min(cur, val);
}

template<typename T>
void relax_max(T& cur, T val) {
    cur = max(cur, val);
}

void precalc() {
}

#define int li
const int mod = 1000000007;

void add(int& cur, int val) {
  cur += val;
  cur %= mod;
}

struct DP {
  array<array<int, 2>, 2> vals;
  DP() {
    for (int i = 0; i < 2; ++i) {
      for (int j = 0; j < 2; ++j) {
        vals[i][j] = 0;
      }
    }
  }
};

void solve(__attribute__((unused)) bool read) {
  int h;
  //read = false;
  if (read) {
    cin >> h;
  } else {
    h = 18;
  }
  int n = (1 << (h - 1));
  vector<int> p(n);
  if (read) {
    for (int &x : p) {
      cin >> x;
      --x;
    }
  } else {
    iota(all(p), 0);
    random_shuffle(all(p));
  }
  vector<vector<int>> products(n, vector<int>(h));
  auto jumps = products;
  auto how = jumps;
  vector<vector<int>> leaves(n * 2);
  vector<int> depth(n * 2);
  for (int i = 0; i < n; ++i) {
    int index = n + i;
    int prod = index;
    int last_how = -1;
    for (int j = 0; j < h; ++j) {
      leaves[index].push_back(i);
      depth[index] = j;
      products[i][j] = prod;
      jumps[i][j] = index;
      how[i][j] = last_how;
      last_how = index % 2;
      index /= 2;
      prod = prod * index % mod;
    }
  }
  array<array<vector<int>, 2>, 2> score;
  array<array<vector<int>, 2>, 2> used;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      score[i][j].assign(n, 0);
      used[i][j].assign(n, 0);
    }
  }
  int TIMER = 0;
  vector<int> used_lower(n, 0);
  vector<int> lowers_to_consider;
  li ans = 0;
  for (int upper = 1; upper < n; ++upper) {
    ++TIMER;
    lowers_to_consider.clear();
    for (int par = 0; par < 2; ++par) {
      auto insert_val = [&] (int lower, int type, int val) {
        if (used[par][type][lower] != TIMER) {
          score[par][type][lower] = 0;
        }
        if (used_lower[lower] != TIMER) {
          used_lower[lower] = TIMER;
          lowers_to_consider.push_back(lower);
        }
        add(score[par][type][lower], val);
        used[par][type][lower] = TIMER;
      };
      for (int v : leaves[2 * upper + par]) {
        //cout << "upper: " << upper << " v: " << v << " depth: " << depth[upper] << " prod: " << products[v][depth[upper] - 1] << endl;
        int to = p[v];
        for (int len2 = 1; len2 < h; ++len2) {
          int lower = jumps[to][len2];
          insert_val(lower, how[to][len2], products[v][depth[upper] - 1] * products[to][len2 - 1]);
        }
      }
    }
    for (int lower : lowers_to_consider) {
      for (int par = 0; par < 2; ++par) {
        if (used[0][par][lower] == TIMER && used[1][par ^ 1][lower] == TIMER) {
          add(ans, score[0][par][lower] * score[1][par ^ 1][lower] % mod * upper % mod * lower);
        }
      }
    }
  }

  cout << ans << "\n";

}