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
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mkp make_pair
#define rint register int
#define INF ((1 << 30) - 1)
#define FI(n) FastIO::read(n)
#define FO(n) FastIO::write(n)
#define Pair pair < int, int >
#define mst(a,b) memset(a,b,sizeof(a))
#define foR(i, k, j) for(int i = (k); i >= (j); i--)
#define For(i, k, j) for(int i = (k); i <= (j); i++)
#define Foe(i, u) for(rint i = lst[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout)
#define int long long
const int P = 1000000007; //
using namespace std;
inline void ckmax(int &a, int b) {a = max(a, b);}
inline void ckmin(int &a, int b) {a = min(a, b);}
inline void mulmod(int &a, int b) {a = 1ll * a * b % P;}
inline void addmod(int &a, int b) {int t = a + b; a = (t >= P ? t - P : t); }
inline void delmod(int &a, int b) {int t = a - b; a = (t < 0 ? t + P : t); }
inline int ksm(int a, int b) {int ans=1; for(;b;b>>=1) {if(b&1) ans=1ll*ans*a%P;a=1ll*a*a%P;}return ans;}
inline int inv(int a) {return ksm(a, P-2);}

inline void printarray(int *a, int n) {For(i, 1, n) fprintf(stderr, "%d ", a[i]); fprintf(stderr, "\n");}
namespace FastIO {
    const int SIZE=1<<16; char buf[SIZE], obuf[SIZE], str[64]; int bi=SIZE, bn=SIZE, opt;
    int read(char *s) {
        while (bn) {for (;bi<bn&&buf[bi]<=' ';bi++);if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}
        int sn=0;while (bn) {for (;bi<bn&&buf[bi]>' ';bi++) s[sn++]=buf[bi];if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}s[sn]=0;return sn;
    }
    bool read(int& x) {if(x)x=0;int bf=0,n=read(str); if(!n) return 0; int i=0; if (str[i]=='-') bf=1,i=1; for(x=0;i<n;i++) x=x*10+str[i]-'0'; if(bf) x=-x; return 1;}
    void write(int x) {
        if(!x) obuf[opt++] = '0'; else {if(x<0) obuf[opt++]='-',x=-x;int sn=0; while(x)str[sn++]=x%10+'0',x/=10;for (int i=sn-1;i>=0;i--) obuf[opt++]=str[i];}
        if (opt>=(SIZE>>1)){fwrite(obuf, 1, opt, stdout); opt=0;}
    }
    void write(char x) {obuf[opt++]=x;if (opt>=(SIZE>>1)){fwrite(obuf, 1, opt, stdout); opt=0;}}
    void Fflush() { if (opt) fwrite(obuf, 1, opt, stdout); opt=0;}
};
const int MAXN = (1 << 19) + 5;
int m, n, p[MAXN], res = 0, v[MAXN], iv[MAXN];
inline int mul(int x, int y) {
//	fprintf(stderr, "mul(%d, %d) = %d\n", x, y, 1ll * x * y % P);
	return 1ll * x * y % P;
}
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mid ((l + r) >> 1)
#define fa (k >> 1)
void init(int k, int l, int r) {
	iv[k] = inv(v[k]); if(l == r) return;
	v[ls] = mul(v[k], ls); v[rs] = mul(v[k], rs);
	init(ls, l, mid); init(rs, mid+1, r);
}
int tmp[MAXN];
inline void add(int k, int val) {
	int st = k;
	while(k) addmod(tmp[k], mul(val, mul(v[st], iv[fa]))), k = fa;
//	cerr << st << ' ' << fa << ' ' << mul(v[st], iv[fa]) << endl;
}
inline void del(int k) {while(k) tmp[k] = 0, k = fa;}
inline int calc(int k) {
	int st = k, res = 0, lst = 0;
	while(k) {
		int tv = mul(v[st], iv[k]);  
		addmod(res, mul(tv, tmp[k] - lst + P) % P); lst = mul(tmp[k], fa);
//		cerr << lst << endl;
		k = fa;
	}
//	cerr << res << endl;
	return res;
}
void solve(int k, int l, int r) {
	if(l == r) return;
	For(i, l, mid) add(p[i] + (n >> 1) - 1, mul(v[i + (n >> 1) - 1], iv[fa]));
	For(i, mid+1, r) addmod(res, mul(calc(p[i] + (n >> 1) - 1), mul(v[i + (n >> 1) - 1], iv[k])));
	For(i, l, mid) del(p[i] + (n >> 1) - 1);
//	For(i, 1, n) assert(tmp[i] == 0);
	solve(ls, l, mid); solve(rs, mid+1, r);
}
signed main()
{
    #ifndef ONLINE_JUDGE
        file("pro");
    #endif
    cin >> m; n = (1 << m);
    For(i, 1, n >> 1) scanf("%d", &p[i]);
    iv[0] = 1; v[1] = 1; init(1, 1, n >> 1);
//    For(i, 1, n) cerr << v[i] << ' ';
    solve(1, 1, n >> 1);
    cout << res << endl;
    
    return FastIO::Fflush(), 0;
}
/*
Think twice :
mod ?
INF ?
n = 1 ?
long long ?
Fastio::Fflush() ?

*/
