题目描述

テレビドラマシリーズ『ストレンジャー・シングス』に触発されたクマのリマクは、現実世界と鏡像世界を歩いて行き来することにしました。

二つの高さ $H$ の完全二分木があり、それぞれの頂点は $1$ から $2^H-1$ までの標準的な番号付けがなされています。 すなわち、根の番号は $1$ で、番号 $x$ の子の番号は $2\ \cdot\ x$ と $2\ \cdot\ x\ +\ 1$ です。

一つの木が持つ葉の数を $L$ とします。すなわち、$L\ =\ 2^{H-1}$ です。

数列 $1,\ \ldots,\ L$ の順列 $P_1,\ P_2,\ \ldots,\ P_L$ が与えられます。これは、二つの木を結ぶ $L$ 本の 特殊辺 を表します。 すなわち、第一の木の番号 $L+i-1$ の頂点と第二の木の番号 $L+P_i-1$ の頂点が一本の特殊辺で結ばれています。

入力例 1 の図示。$P\ =\ (2,\ 3,\ 1,\ 4)$ であり、緑の辺が特殊辺

サイクルの 積 を、それに含まれる頂点の番号の積と定義します。ちょうど二本の特殊辺を持つような すべての単純サイクルの積の和を $(10^9+7)$ で割った余りを求めてください。

なお、単純サイクルとは、長さが $3$ 以上であって頂点や辺の重複がないようなサイクルです。

输入格式

入力は以下の形式で標準入力から与えられる (ここで、$L\ =\ 2^{H-1}$ である)。

$H$ $P_1$ $P_2$ $\cdots$ $P_L$

输出格式

ちょうど二本の特殊辺を持つようなすべての単純サイクルの積の和を求め、それを $(10^9+7)$ で割った余りを出力せよ。

题目大意

给定两棵完全相同的 $n$ 层完全二叉树，其中第 $i$ 层编号依次为 $2^{i-1},2^{i-1}+1,\dots, 2^i−1$。

给定一个 $1$ 到 $2^{n-1}$ 的排列 $p$，将第一棵树的第 $i$ 个叶子节点连向第二棵树的第 $p_i$ 个叶子节点。

求此图中合法的环的权值和。

称一个环合法当且仅当它恰好经过 $2$ 条非树边，定义一个环的权值为环上点的编号乘积。

答案对 $10^9 + 7$ 取模。

$2 \le n \le 18$。

3
2 3 1 4

121788

2
1 2

36

5
6 14 15 7 12 16 5 4 11 9 3 10 8 2 13 1

10199246

提示

制約

• $2\ \leq\ H\ \leq\ 18$
• $1\ \leq\ P_i\ \leq\ L$ (ただし $L\ =\ 2^{H-1}$)
• $P_i\ \neq\ P_j$ (すなわち、この数列は $1,\ \ldots,\ L$ の順列である)

Sample Explanation 1

下図に考慮すべきサイクルを二つ示します (他にも存在します)。一つめのサイクルの積は $ 2\ \cdot\ 5\ \cdot\ 6\ \cdot\ 3\ \cdot\ 1\ \cdot\ 2\ \cdot\ 5\ \cdot\ 4\ =\ 7200 $、二つめのサイクルの積は $ 1\ \cdot\ 3\ \cdot\ 7\ \cdot\ 7\ \cdot\ 3\ \cdot\ 1\ \cdot\ 2\ \cdot\ 5\ \cdot\ 4\ \cdot\ 2\ =\ 35280 $ です。三つめのサイクルは、特殊辺の数が二本でないため、考慮すべきサイクルではありません。 

Sample Explanation 2

グラフ中の唯一のサイクルは確かに特殊辺を二本持ち、その頂点番号の積は $ 1\ \cdot\ 3\ \cdot\ 3\ \cdot\ 1\ \cdot\ 2\ \cdot\ 2\ =\ 36 $ です。