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
import java.util.*;
import java.io.*;

class Main {
  final static int mod = 1000000000 + 7;
  static long [] sum;
  static void addValue(int node, long value) {
    while(node > 0) {
      value = (value * node) % mod;
      sum[node] = (sum[node] + value) % mod;
      node >>= 1;
    }
  }
  static long getSum(int node, long value) {
    long ans = 0;
    while(node > 1) {
      value = (value * node) % mod;
      long product = (value * (node >> 1)) % mod;
      ans = (ans + product * sum[node ^ 1]) % mod;
      node >>= 1;
    }
    return ans;
  }
  static long pathProduct(int cur, int root) {
    long product = 1;
    while(true) {
      product = (product * cur) % mod;
      if(cur == root) break;
      cur >>= 1;
    }
    return product;
  }
  public static void main(String [] args) {
    Reader in = new Reader();
    int h = in.nextInt();
    int n = (1 << (h - 1));
    int [] a = new int [n];
    sum = new long [1 << h];
    for(int i = 0; i < n; i++) {
      a[i] = in.nextInt() - 1;
    }
    long ans = 0;
    for(int i = 1; i < n; i++) {
      int [] left = getIndex(2 * i, h);
      int [] right = getIndex(2 * i + 1, h);
      for(int j : left) {
        addValue(a[j - n] + n, pathProduct(j, 2 * i));  
      }
      for(int j : right) {
        ans = (ans + getSum(a[j - n] + n, pathProduct(j, i))) % mod; 
      }
      for(int j : left) {
        addValue(a[j - n] + n, (mod - pathProduct(j, 2 * i)) % mod);
      }
    }
    System.out.println(ans);
  }
  static int msb(int value) {
    for(int i = 31; i >= 0; i--) {
      if(((value >> i) & 1) == 1) {
        return i;
      }
    }
    return 0;
  }
  static int [] getIndex(int node, int h) {
    int remaining = h - msb(node) - 1;
    int [] a = new int [1 << remaining];
    for(int i = 0; i < (1 << remaining); i++) {
      a[i] = node * (1 << remaining) + i;
    }
    return a;
  }
}

class Reader {
  BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  StringTokenizer s = new StringTokenizer("");
  Reader () {}
  String nextLine() {
    try {
      return in.readLine();
    } catch (Exception e) {
      e.printStackTrace();
      return "Error";
    }
  }
  String next() {
    while(!s.hasMoreTokens()) {
      s = new StringTokenizer(nextLine());
    }
    return s.nextToken();
  }
  int nextInt() {
    return Integer.parseInt(next());
  }
}

