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>

using namespace std;
typedef long long ll;
const int MAXN = (1 << 18) + 100;
const ll MOD = 1e9 + 7;

ll cpow (ll b, int e)
{
    if (e == 0) return 1;
    if (e == 1) return (b % MOD);
    ll v = cpow (b, e / 2);
    v = (v * v) % MOD;
    if (e % 2 == 1) v = (v * b) % MOD;
    return v;
}

ll inv (ll x)
{
    return cpow (x, MOD - 2);
}

ll mscore[MAXN];
ll iscore[MAXN];

int L, N;
int ncross[MAXN];
ll np[MAXN];

pair <ll, ll> ps[MAXN];

int main()
{
    ios_base::sync_with_stdio(0);

    mscore[0] = 1;
    iscore[0] = 1;
    mscore[1] = 1;
    for (int i = 2; i < (1 << 18); i++)
    {
        mscore[i] = (i * mscore[i/2]) % MOD;
    }
    for (int i = 1; i < (1 << 18); i++)
        iscore[i] = inv ((mscore[i] * mscore[i/2]) % MOD);

    cin >> L;
    N = (1 << (L - 1));
    for (int i = 0; i < N; i++)
    {
        cin >> ncross[i];
        ncross[i]--;
        np[i] = (mscore[i+N] * mscore[ncross[i]+N]) % MOD;
    }

    ll ans = 0;
    for (int i = 0; i < L - 1; i++)
        for (int j = 0; j < L - 1; j++)
        {
            unordered_map <int, pair <ll, ll> > mm;
            for (int k = 0; k < N; k++)
            {
                int v = ncross[k] >> (L - 1 - j);
                int b1 = (k >> (L - 2 - i) & 1);
                int b2 = (ncross[k] >> (L - 2 - j)) & 1;
                v = 2 * v + (b1 ^ b2);
                if (b2)
                    mm[v].second += np[k];
                else
                    mm[v].first += np[k];

                if ((k + 1) % (1 << (L - 1 - i)) == 0)
                {
                    for (auto it = mm.begin(); it != mm.end(); it++)
                    {
                        if (!it->second.first || !it->second.second) continue;
                        ll l = it->second.first % MOD, l2 = it->second.second % MOD;
                        //cout << i << " " << j << " " << l << " " << l2 << "\n";

                        ll v = (l * l2) % MOD;
                        ll mask = it->first;
                        int a1 = (1<<i) + (k >> (L - 1 - i));
                        int a2 = (1<<j) + (mask / 2) % (1 << j);
                        //cout << mask << " " << a1 << " " << a2 << "\n";
                        v = v * (iscore[a1]) % MOD;
                        v = v * (iscore[a2]) % MOD;
                        ans += v;
                    }
                    mm.clear();
                }
            }
        }
    ans %= MOD;
    cout << ans << "\n";
}