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 <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long int int64;

const int MOD = (int) 1e9 + 7;

void sadd(int &a, int b)
{
    a += b;
    if (a >= MOD)
        a -= MOD;
}
int add(int a, int b)
{
    sadd(a, b);
    return a;
}
int mul(int a, int b)
{
    return (a * 1LL * b) % MOD;
}


const int N = (int) 3e5 + 100;
int vs[2][2][N];
int vx[2][2][N];
int vsz[2][2];

int n;

pair <int, int> val[N];

void sortVs(int id)
{
    for (int i = 0; i < vsz[id][0]; i++)
        val[i] = make_pair(vs[id][0][i], vx[id][0][i]);
    sort(val, val + vsz[id][0]);
    for (int i = 0; i < vsz[id][0]; i++)
    {
        vs[id][0][i] = val[i].first;
        vx[id][0][i] = val[i].second;
    }
}

void getList(int id, int v)
{
    int t = 0, nt = 1;
    vsz[id][t] = 1;
    vs[id][t][0] = v;
    vx[id][t][0] = v;

    while (vs[id][t][0] < n)
    {
        if (vsz[id][t] == 0) throw;
        vsz[id][nt] = 0;
        for (int i = 0; i < vsz[id][t]; i++)
        {
            int x = vs[id][t][i];
            int xx = vx[id][t][i];
            int sz = vsz[id][nt];
            
            vx[id][nt][sz] = mul(xx, 2 * x);
            vx[id][nt][sz + 1] = mul(xx, 2 * x + 1);
            vs[id][nt][sz] = 2 * x;
            vs[id][nt][sz + 1] = 2 * x + 1;

            vsz[id][nt] += 2;

        }
        swap(t, nt);
    }
    vsz[id][nt] = vsz[id][t];
    for (int i = 0; i < vsz[id][t]; i++)
        vs[id][nt][i] = vs[id][t][i];
    for (int i = 0; i < vsz[id][t]; i++)
        vx[id][nt][i] = vx[id][t][i];
}

int getAns()
{
    int p1p = 0;
    int p1m = 0;

    int ans = 0;
    for (int p0 = 0; p0 < vsz[0][0]; p0++)
    {
        while (p1p < vsz[1][0] && vs[1][0][p1p] < vs[0][0][p0] + 1)
            p1p++;
        while (p1m < vsz[1][0] && vs[1][0][p1m] < vs[0][0][p0] - 1)
            p1m++;

        if (vs[0][0][p0] % 2 == 0)
        {
            if (p1p < vsz[1][0] && vs[1][0][p1p] == vs[0][0][p0] + 1)
                sadd(ans, mul(mul(vx[0][0][p0], vx[1][0][p1p]), vs[0][0][p0] / 2));
        }
        else
        {
            if (p1m < vsz[1][0] && vs[1][0][p1m] == vs[0][0][p0] - 1)
                sadd(ans, mul(mul(vx[0][0][p0], vx[1][0][p1m]), vs[0][0][p0] / 2));
        }
    }
    return ans;
}

void eprintLists()
{
    for (int id = 0; id < 2; id++)
    {
        eprintf("--- id = %d ---\n", id);
        for (int i = 0; i < vsz[id][0]; i++)
            eprintf("%d (%d); ", vs[id][0][i], vx[id][0][i]);
        eprintf("\n");
    }
}

void goUp(int id)
{
    for (int i = 0; i < vsz[id][0]; i++)
    {
        vs[id][0][i] /= 2;
        vx[id][0][i] = mul(vx[id][0][i], vs[id][0][i]);
    }
    int sz = 0;
    for (int i = 0; i < vsz[id][0]; i++)
    {
        if (sz == 0 || vs[id][0][i] != vs[id][0][sz - 1])
        {
            vs[id][0][sz] = vs[id][0][i];
            vx[id][0][sz] = vx[id][0][i];
            sz++;
        }
        else
        {
            sadd(vx[id][0][sz - 1], vx[id][0][i]);
        }
    }
    vsz[id][0] = sz;
}

int p[N];

int main(int,  char **)
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

    int h;
    scanf("%d", &h);
    h--;

    n = (1 << h);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &p[i]);
        p[i]--;
    }

    int answer = 0;

    for (int v = 1; v < n; v++)
    {
        //eprintf("v = %d\n", v);
        int cans = 0;
        int a = 2 * v, b = 2 * v + 1;
        getList(0, a);
        getList(1, b);

        //eprintLists();

        //eprintf("got lists\n");
        for (int id = 0; id < 2; id++)
        {
            for (int i = 0; i < vsz[id][0]; i++)
            {
                vs[id][0][i] = n + p[vs[id][0][i] - n];
                vx[id][0][i] = mul(vx[id][0][i], vs[id][0][i]);
            }
            sortVs(id);
        }

        while (vs[0][0][0] > 1)
        {
            //eprintLists();
            sadd(cans, getAns());

            goUp(0);
            goUp(1);
        }

        cans = mul(cans, v);
        sadd(answer, cans);
    }


    printf("%d\n", answer);


	return 0;
}


