p02591 AtCoder Grand Contest 047 - Twin Binary Trees
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
```python
#import random,time

H=int(input())
#P=[i for i in range(2**(H-1))]
#random.shuffle(P)
P=list(map(lambda x:int(x)-1,input().split()))
mod=10**9+7
inv=pow(2,mod-2,mod)

L=2**(H-1)

base_t=[1 for i in range(1+1<<H)]
base_t[0]=0
for i in range(2,1+1<<H):
    base_t[i]=i*base_t[i>>1]
    base_t[i]%=mod

base_s=[(i*pow(base_t[i]**2,mod-2,mod))%mod for i in range(1+1<<H)]

ans=0
def solve(i):
    global ans
    if i>=L:
        i-=L
        val=(base_t[i+L]*base_t[P[i]+L])%mod
        val2=pow(val,2,mod)
        id=P[i]+L
        res=[[(P[i]+L)>>(H-1-j),val,val2] for j in range(H)]
        return res
    L1=solve(2*i)
    L2=solve(2*i+1)
    Li,ttt=merge(L1,L2)
    ttt=(ttt*(base_s[i]-base_s[i>>1]))%mod
    ans=(ans+ttt)%mod
    return Li

def merge(L1,L2):
    res=[]
    L1.append([10**18,0])
    L2.append([10**18,0])
    L1=L1[::-1]
    L2=L2[::-1]
    ttt=0
    if L1[-1][0]<=L2[-1][0]:
        res.append(L1.pop())
    else:
        res.append(L2.pop())
    while L1 and L2:
        if L1[-1][0]<=L2[-1][0]:
            if res and res[-1][0]==L1[-1][0]:
                res[-1][1]+=L1[-1][1]
                res[-1][1]%=mod
                res[-1][2]+=L1[-1][2]
                res[-1][2]%=mod
                L1.pop()
            else:
                j,val,val2=res[-1]
                tmp=(base_s[j]-base_s[j>>1]) %mod
                c=val**2 %mod
                c=(c-val2)%mod
                tmp =(tmp*c) %mod
                ttt=(ttt+tmp)%mod
                res.append(L1.pop())
        else:
            if res and res[-1][0]==L2[-1][0]:
                res[-1][1]+=L2[-1][1]
                res[-1][1]%=mod
                res[-1][2]+=L2[-1][2]
                res[-1][2]%=mod
                L2.pop()
            else:
                j,val,val2=res[-1]
                tmp=(base_s[j]-base_s[j>>1]) %mod
                c=val**2 %mod
                c=(c-val2)%mod
                tmp =(tmp*c) %mod
                ttt=(ttt+tmp)%mod
                res.append(L2.pop())
    res.pop()
    return res,ttt

solve(1)

print(ans*inv %mod)

```