题目描述

受到电视剧《怪奇物语》的启发，小熊 Limak 在两个镜像世界间散步。

有两个高度为 $H$ 的完美二叉树，每个树节点的编号从 $1$ 到 $2^H-1$。根节点是 $1$，第 $x$ 个节点的子节点是 $2 \\cdot x$ 和 $2 \\cdot x + 1$。

用 $L$ 表示单棵树的叶子节点数量，即 $L = 2^{H-1}$。

给定一个由 $1$ 到 $L$ 的数字组成的排列 $P_1, P_2, \\ldots, P_L$。它描述了连接两棵树叶子节点的 $L$ 条特殊边。第一棵树中的节点 $L+i-1$ 和第二棵树中的节点 $L+P_i-1$ 之间存在一条特殊边。

第一个示例测试的图，排列 $P = (2, 3, 1, 4)$，绿色表示特殊边

现在，我们将一个环路的定义扩展为路径上所有点的乘积。求所有恰好含有两条特殊边的简单环路的乘积之和，结果对 $(10^9+7)$ 取模。

这里的简单环路是长度至少为 3 的环路，其中没有重复的节点或边。

约束条件

• $2 \\leq H \\leq 18$
• $1 \\leq P_i \\leq L$ 其中 $L = 2^{H-1}$
• $P_i \\neq P_j$（因此这是一个排列）

输入

输入以标准输入给出，格式如下所示（其中 $L = 2^{H-1}$）。

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

输出

计算恰好含有两条特殊边的简单环路的乘积之和，并将答案对 $(10^9+7)$ 取模后打印出来。

示例输入 1

3
2 3 1 4

示例输出 1

121788

以下画出了两个有效的环路（但还有更多！），它们的乘积分别是 $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$。第三个环路是无效的，因为它没有恰好两条特殊边。

示例输入 2

2
1 2

示例输出 2

36

图中唯一的简单环路确实有两条特殊边，且节点乘积为 $1 \\cdot 3 \\cdot 3 \\cdot 1 \\cdot 2 \\cdot 2 = 36$。

示例输入 3

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

示例输出 3

10199246