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 <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

const int md = 1e9 + 7;

int mul(int a, int b) {
  return ((ll)a * b) % md;
}

void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

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

int power(int a, ll b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = mul(res, a);
    a = mul(a, a);
    b >>= 1;
  }
  return res;
} 

int inv(int x) {
  return power(x, md - 2);
}

const int N = 3e5 + 7;

int sum[N];
int pr[N];
int ip[N];

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int h;
  cin >> h;
  int n = (1 << h) - 1;
  int L = (1 << (h - 1));
  vector <int> p(L);
  for (int i = 0; i < L; ++i) {
    cin >> p[i];
    p[i] += L - 1;
  }
  pr[1] = 1;
  for (int i = 2; i < N; ++i) {
    pr[i] = mul(pr[i / 2], i);
  }
  for (int i = 1; i < N; ++i) {
    ip[i] = inv(pr[i]);
  }
  auto add_ver = [&] (int v, int x) {
    while (v > 0) {
      add(sum[v], x);
      v /= 2;
    }
  };  
  auto del_ver = [&] (int v, int x) {
    while (v > 0) {
      sub(sum[v], x);
      v /= 2;
    }
  };  

  auto get_dv = [&] (int u) {
    int dv = mul(mul(ip[u], ip[u]), u);
    return dv;
  };

  vector <vector <int>> who(n + 1);
  for (int x = (1 << (h - 1)); x <= n; ++x) {
    int v = x;
    while (v > 0) {
      who[v].push_back(x);
      v /= 2;
    } 
  } 

  int ans = 0;
  for (int u = 1; u < L; ++u) {
    int l = 2 * u;
    int r = 2 * u + 1;
    int cur_sum = 0;
    int dv = get_dv(u);
    for (auto v : who[l]) {
      add_ver(p[v - L], mul(pr[v], pr[p[v - L]]));
    }
    for (auto v : who[r]) {
      int w = p[v - L];
      int go = mul(pr[v], pr[w]);
      while (w != 1) {
        int par = w / 2;
        int other_w = w ^ 1;
        
        add(cur_sum, mul(mul(go, sum[other_w]), get_dv(par))); 
        w = par;
      }
    }

    for (auto v : who[l]) {
      del_ver(p[v - L], mul(pr[v], pr[p[v - L]]));
    }
    add(ans, mul(cur_sum, dv));
  }
  cout << ans << '\n';
}

