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>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ldb;
typedef complex<double> base;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const bool debug=false;
const ll mod=1e9+7;
ll exp(ll x,ll y){if(y<0) return 0; ll ret=1;for(;y;y>>=1,x=(x*x)%mod){if(y&1)ret=(ret*x)%mod;}return ret;}

ll H, L, ans;
ll P[25+(1<<17)];
ll DP[25+(1<<18)];
ll IV[25+(1<<18)];

struct PST
{
	int root[555555];
	int lc[11111111], rc[11111111];
	ll val[11111111], nex;
	void build(void)
	{
		root[0]=1; nex=(1<<(H));
    	for(int i=1 ; i<(1<<(H-1)) ; i++) lc[i]=(i<<1), rc[i]=(i<<1|1);
	}
	int copy(int cur)
	{
	    int x=++nex;
	    val[x]=val[cur]; lc[x]=lc[cur]; rc[x]=rc[cur];
	    return x;
	}
	int update(int cur, int s, int e, int l, int r, ll v) 
	{
	    if(l>e || r<s) return cur;
	    int x=copy(cur);
	    if(l<=s && e<=r)
	    {
	        val[x]+=v;
	      	if(val[x]>=mod) val[x]-=mod;
	        return x;
	    }
	    int m=(s+e)>>1;
	    lc[x]=update(lc[x],s,m,l,r,v);
	    rc[x]=update(rc[x],m+1,e,l,r,v);
		val[x]=val[lc[x]]+val[rc[x]];
		if(val[x]>=mod) val[x]-=mod;
   		return x;
	}
	ll eval(int cur, int loc, int s, int e, int l, int r, int HD)
	{
		ll ret=0, m=(s+e)>>1;
		if(s==HD-1 && e==HD-1) return 0;
		if(s<=HD-1 && HD-1<=m)
		{
			// m+1 ~ e is ok
			ret=val[rc[cur]];
			ret=(ret*IV[loc])%mod;
			ret=(ret*IV[loc>>1])%mod;
			ret+=eval(lc[cur], loc<<1, s, m, l, r, HD);
			if(ret>=mod) ret-=mod; return ret;
		}
		else
		{
			ret=val[lc[cur]];
			ret=(ret*IV[loc])%mod;
			ret=(ret*IV[loc>>1])%mod;
			ret+=eval(rc[cur], loc<<1|1, m+1, e, l, r, HD);
			if(ret>=mod) ret-=mod; return ret;
		}
	}
} PT;

// indexing is fucked up please

int main(void)
{
	fio; ll i, j, add; cin>>H; L=(1<<(H-1));
	for(i=1 ; i<=L ; i++) cin>>P[i];
	PT.build(); DP[0]=1; IV[0]=1; DP[1]=1; IV[1]=1;	
	for(i=2 ; i<=(1<<H) ; i++) DP[i]=(DP[i/2]*i)%mod;
	for(i=2 ; i<=(1<<H) ; i++) IV[i]=exp(DP[i], mod-2);
	ll fuck=0;
	for(i=1 ; i<=L ; i++) fuck+=(DP[L+i-1]*DP[L+P[i]-1])%mod;
	for(i=1 ; i<=L ; i++) PT.root[i]=PT.update(PT.root[i-1], 0, (1<<(H-1))-1, P[i]-1, P[i]-1, (DP[L+i-1]*DP[L+P[i]-1])%mod);
	for(i=1 ; i<=L ; i++)
	{
		ll cL=L+i-1, cR=L+i-1, p2=1, nL, nR;
		for(j=1 ; j<=H-1 ; j++)
		{
			p2<<=1; 
			if(cL%p2==0) 
			{
				nL=cL+(p2>>1);
				nR=cR+(p2>>1);
				add=PT.eval(PT.root[nR-L+1], 1, 0, (1<<(H-1))-1, 0, (1<<(H-1))-1, P[i]);
				add-=PT.eval(PT.root[nL-1-L+1], 1, 0, (1<<(H-1))-1, 0, (1<<(H-1))-1, P[i]);
				add+=mod; if(add>=mod) add-=mod;
				add=(add*DP[L+i-1])%mod; 
				add=(add*DP[L+P[i]-1])%mod;
				add=(add*IV[(L+i-1)>>j])%mod;
				add=(add*IV[(L+i-1)>>(j+1)])%mod;
				ans+=add; if(ans>=mod) ans-=mod;
				cL=min(cL, nL); cR=max(cR, nR);
			}
			else
			{
				nL=cL-(p2>>1);
				nR=cR-(p2>>1);
				add=PT.eval(PT.root[nR-L+1], 1, 0, (1<<(H-1))-1, 0, (1<<(H-1))-1, P[i]);
				add-=PT.eval(PT.root[nL-1-L+1], 1, 0, (1<<(H-1))-1, 0, (1<<(H-1))-1, P[i]);
				add+=mod; if(add>=mod) add-=mod;
				add=(add*DP[L+i-1])%mod; 
				add=(add*DP[L+P[i]-1])%mod;
				add=(add*IV[(L+i-1)>>j])%mod;
				add=(add*IV[(L+i-1)>>(j+1)])%mod;
				ans+=add; if(ans>=mod) ans-=mod;
				cL=min(cL, nL); cR=max(cR, nR);
			}
		}
	}	
	ans=(ans+100LL*mod)%mod;
	ans=(ans*exp(2, mod-2))%mod;
	cout<<ans%mod; return 0;
}
