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
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)

mt19937 Rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

template <typename T>
inline void chkmax(T &x, T y) { if (x < y) x = y; }

template <typename T>
inline void chkmin(T &x, T y) { if (x > y) x = y; }

inline int read() {
  #define nc getchar()
  int x = 0;
  char c = nc;
  while (c < 48) c = nc;
  while (c > 47) x = x * 10 + (c ^ 48), c = nc;
  return x;
  #undef nc
}

const int P = 1e9 + 7;

int Inc(int x, int y) {
  return x + y < P ? x + y : x + y - P;
}

int Dec(int x, int y) {
  return x < y ? x - y + P : x - y;
}

void Add(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}

void Sub(int &x, int y) {
  x -= y;
  if (x < 0) x += P;
}

int qp(int a, int k) {
  int res = 1;
  for (; k; k >>= 1, a = 1ll * a * a % P) {
    if (k & 1) res = 1ll * res * a % P;
  }
  return res;
}

typedef long long ll;
const int maxn = 1 << 18 | 5;
int H, n, A[maxn];

//int sum[maxn];
//int prod[maxn], invp[maxn];

//void dfs(int u, int dep) {
//  prod[u] = 1ll * u * prod[u >> 1] % P, invp[u] = qp(prod[u], P - 2);
//  if (dep == H) sum[u] = prod[u];
//  if (dep < H) dfs(u << 1, dep + 1), dfs(u << 1 | 1, dep + 1), sum[u] = Inc(sum[u << 1], sum[u << 1 | 1]);
//}

int ans;
int T, sub[maxn], tim[maxn];

void dfs1(int u, int val) {
  if (u * 2 > n + n - 1) {
    int pos = n + A[u - n + 1] - 1;
    while (pos) {
      if (tim[pos] != T) {
        tim[pos] = T, sub[pos] = 0;
      }
      val = 1ll * val * pos % P;
      Add(sub[pos], val);
      pos >>= 1;
//      printf("#%d %d\n", pos, val);
    }
    return;
  }
  dfs1(u << 1, 1ll * (u << 1) * val % P), dfs1(u << 1 | 1, 1ll * (u << 1 | 1) * val % P);
}

void dfs2(int u, int val) {
  if (u * 2 > n + n - 1) {
//    printf("#%d\n", u);
    int pos = n + A[u - n + 1] - 1;
//      printf("#%d\n",pos);
    while (pos) {
      if (tim[pos ^ 1] != T) {
        tim[pos ^ 1] = T, sub[pos ^ 1] = 0;
      }
//      printf("#%d %d\n", pos, val);
      val = 1ll * val * pos % P;
      ans = (ans + 1ll * sub[pos ^ 1] * val % P * (pos >> 1)) % P;
      pos >>= 1;
    }
    return;
  }
  dfs2(u << 1, 1ll * (u << 1) * val % P), dfs2(u << 1 | 1, 1ll * (u << 1 | 1) * val % P);
}

void solve() {
  cin >> H;
  n = 1 << (H - 1);
  rep(i, 1, n) A[i] = read();
//  prod[0] = 1, invp[0] = 1;
//  dfs(1, 1);
  rep(anc, 1, n - 1) {
    T = anc;
    int lef = anc << 1, rig = anc << 1 | 1;
    dfs1(lef, 1ll * anc * lef % P);
    dfs2(rig, rig);
  }
  cout << ans << endl;
}

int main() {
//  int T = read();
//  while (T--) solve();
  solve();
  return 0;
}