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 <vector>
#include <algorithm>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 18;
int const modulo = 1000000007;
int p[1 + (1 << nmax)];

void dfs(int node, int offset, int acc, std::vector<std::pair<int,int>> &sons) {
  acc = 1LL * acc * node % modulo;
  if(offset < node) {
    sons.push_back({node - offset, acc});
  } else {
    dfs(node * 2, offset, acc, sons);
    dfs(node * 2 + 1, offset, acc, sons);
  } 
}
int sum[2][1 + (1 << nmax)];

void gcd(int a, int b, int &x, int &y) {
  if(b == 0) {
    x = 1;
    y = 0;
  } else {
    gcd(b, a % b, x, y);
    int aux = x;
    x = y;
    y = aux - a / b * y;
  }
}

int inv(int number) {
  int x, y;
  gcd(number, modulo, x, y);
  x %= modulo;
  if(x < 0)
    x += modulo;
  return x;
}

void clearnode(int node, int offset, int &result) {
  if(sum[0][node] == 0 && sum[1][node] == 0)
    return ;
  if(1 < node)
    clearnode(node / 2, offset, result);

  if(node <= offset) {
    result += 1LL * node * ((1LL * sum[0][node * 2] * sum[1][node * 2 + 1] + 1LL * sum[1][node * 2] * sum[0][node * 2 + 1]) % modulo) % modulo;
    if(modulo <= result)
      result -= modulo;
  }

  sum[0][node] = sum[1][node] = 0;
}

void update(int node, int acc, int p) {
  acc = 1LL * acc * node % modulo;
  sum[p][node] += acc;
  if(modulo <= sum[p][node])
    sum[p][node] -= modulo;
  if(1 < node)
    update(node / 2, acc, p);
}

int main() {
  int n;
  std::cin >> n;
  int lim = (1 << n);
  int offset = (1 << (n - 1)) - 1;
  for(int i = 1;i <= (1 << (n - 1)); i++)
    std::cin >> p[i];
  int result = 0;
  for(int i = 1; i <= offset; i++) {
    std::vector<std::pair<int,int>> sons;
    dfs(i, offset, 1, sons);
    int half = sons.size() / 2;
    
    for(int i = 0; i < half; i++)
      update(offset + p[sons[i].first], sons[i].second, 0);
    
    for(int i = half; i < sons.size(); i++)
      update(offset + p[sons[i].first], sons[i].second, 1);
    int result2 = 0; 
    for(int i = 0; i < sons.size(); i++)
      clearnode(offset + p[sons[i].first], offset, result2);

    result += 1LL * inv(i) * result2 % modulo;
    if(modulo <= result)
      result -= modulo;
  }
  std::cout << result;
  return 0;
}
