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>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back  
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll    

const int MOD = 1e9 + 7;
inline void add(int &a, int b) {
  a += b;
  if (a >= MOD) {
    a -= MOD;
  }
}

inline void sub(int &a, int b) {
  a -= b;
  if (a < 0) {
    a += MOD;
  }
}

inline int mult(int a, int b) {
  return (a * 1ll * b) % MOD;
}

int b_pow(int a, int b) {
  if (!b) {
    return 1;
  }
  if (b & 1) {
    return mult(a, b_pow(a, b - 1));
  }
  return b_pow(mult(a, a), b >> 1);
}

const int N = (1 << 18);
int prod[N], inv_prod[N], mn[N], mx[N], to[N], sum[N];

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); 
  cout.tie(0);
  int h;
  cin >> h;
  prod[0] = inv_prod[0] = 1;
  for (int i = 1; i < (1 << h); i++) {
    prod[i] = mult(prod[i / 2], i);
    inv_prod[i] = mult(inv_prod[i / 2], b_pow(i, MOD - 2));
    //cout << prod[i] << ' ' << inv_prod[i] 
  }
  for (int i = (1 << (h - 1)); i < (1 << h); i++) {
    cin >> to[i];
    //cout << i << ' ' << to[i] << endl;
    to[i] += (1 << (h - 1)) - 1;
    mn[i] = mx[i] = i;
  }
  for (int i = (1 << (h - 1)) - 1; i >= 1; i--) {
    mn[i] = mn[2 * i];
    mx[i] = mx[2 * i + 1];
  }
  int ans = 0;
  for (int lca = 1; lca < (1 << (h - 1)); lca++) {
    for (int i = mn[2 * lca]; i <= mx[2 * lca]; i++) {
      int vl = mult(prod[i], inv_prod[lca]), 
      cur = to[i];
      //cout << vl << '\n';
      while (cur) {
        vl = mult(vl, cur);
        add(sum[cur], vl);
        cur /= 2;
      }
    }
    for (int v = mn[2 * lca + 1]; v <= mx[2 * lca + 1]; v++) {
      int u = to[v], cs = 0, vl = mult(u, mult(prod[v], inv_prod[lca / 2]));
      while (u > 1) {
        int lca2 = u / 2, w = (u ^ 1);
        //cout << lca << ' ' << v << ' ' << u << ' ' << lca2 << ' ' << w << ' ' << sum[w] << '\n';
        vl = mult(vl, lca2);
        add(ans, mult(sum[w], vl));
        u /= 2;
      }
    }
    for (int i = mn[2 * lca]; i <= mx[2 * lca]; i++) {
      int vl = mult(prod[i], inv_prod[lca]);
      int cur = to[i];
      while (cur) {
        vl = mult(vl, cur);
        sub(sum[cur], vl);
        cur /= 2;
      }
    }    
  }

  cout << ans << '\n';
} 