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;
typedef long long ll;
typedef pair<int,int> pii;
#define fir first
#define sec second
#define rep(i,a,b) for (int i = (a); i <= (b); ++ i)
#define rrp(i,a,b) for (int i = (a); i >= (b); -- i)
#define gc() getchar()
template <typename tp>
inline void read(tp& x) {
  x = 0; char tmp; bool key = 0;
  for (tmp = gc(); !isdigit(tmp); tmp = gc())
    key = (tmp == '-');
  for (; isdigit(tmp); tmp = gc())
    x = (x << 3) + (x << 1) + (tmp ^ '0');
  if (key) x = -x;
}
template <typename tp>
inline void ckmn(tp& x,tp y) {
  x = x < y ? x : y;
}
template <typename tp>
inline void ckmx(tp& x,tp y) {
  x = x < y ? y : x;
}

const int MOD = (int)(1e9 + 7);
inline void Add(int& x,int y) {
  x = x + y >= MOD ? x + y - MOD : x + y;
}
inline void Sub(int& x,int y) {
  x = x - y < 0 ? x - y + MOD : x - y;
}
int power(int a,int b) {
  int ret = 1;
  while (b) {
    if (b&1) ret = (ll)ret * a % MOD;
    a = (ll)a * a % MOD;
    b >>= 1;
  }
  return ret;
}

const int N = 300010;
int per[N], n, h, dfn[N], sz[N], dcnt, val[N], ival[N];
int ans;
void dfs(int pos) {
  dfn[pos] = ++ dcnt;
  sz[pos] = 1;
  if (2 * pos + 1 <= n) {
    rep (a, 0, 1) {
      dfs(2 * pos + a);
      sz[pos] += sz[2 * pos + a];
    }
  }
}
typedef pair<pii,int> piii;
vector<piii> vec;
void fsd(int pos,int sgn) {
  if (2 * pos + 1 <= n) {
    fsd(2 * pos, sgn);
    fsd(2 * pos + 1, sgn);
  } else {
    vec.push_back(
      make_pair(pii((n / 2) + per[pos - (n / 2)], val[pos]), sgn)
      );
  }
}
int sta[N], top, num[N];
bool insub(int a,int b) {
  return dfn[a] >= dfn[b] && dfn[a] < dfn[b] + sz[b];
}
int lca(int a,int b) {
  if (!a || !b) return a + b;
  while (a != b) {
    if (a > b) a >>= 1;
    else b >>= 1;
  }
  return a;
}
int doit(int rt) {
  vec.clear();
  fsd(2 * rt, 0), fsd(2 * rt + 1, 1);
  sort(vec.begin(), vec.end(), [=](piii a,piii b) -> bool {
    return a.fir.fir < b.fir.fir;
  });
  int ret = 0;
  rep (sgn, 0, 1) {
    top = 0;
    rep (i, 0, (int)vec.size()-1) {
      int p = vec[i].fir.fir;
      int las = 0, rec = 0;
      while (top >= 1 && !insub(p, sta[top])) {
        Add(rec, num[top]);
        las = sta[top --];
      }
      int tmp = lca(las, p);
      if (sta[top] == tmp) Add(num[top], rec);
      else {
        sta[++ top] = tmp;
        num[top] = rec;
      }
      if (vec[i].sec == sgn) {
        if (sta[top] != p) sta[++ top] = p, num[top] = 0;
        Add(num[top], (ll)vec[i].fir.sec * val[p] % MOD);
      } else {
        int tv = (ll)vec[i].fir.sec * val[p] % MOD;
        rep (a, 1, top) Add(ret, (ll)tv * num[a] % MOD * ival[sta[a]] % MOD);
      }
    }
  }
  ret = (ll)ret * ival[rt] % MOD;
  return ret;
}
int main() {
  read(h);
  n = (1 << h) - 1;
  rep (i, 1, (n+1)/2) read(per[i]);
  dfs(1);
  rep (i, 1, n) {
    val[i] = i;
    if (i > 1) val[i] = (ll)val[i] * val[i >> 1] % MOD;
    ival[i] = power(val[i], MOD - 2);
  }
  rrp (i, n, 1) {
    if (i > 1) ival[i] = (ll)ival[i] * ival[i >> 1] % MOD;
  }
  rep (i, 1, n / 2)
    Add(ans, doit(i));
  printf("%d\n", ans);
  return 0;
}