分数: 1000 点
问题陈述
灵感来自电视剧 怪奇物语,熊利马克正在两个镜像世界之间散步。
有两棵高度完美的二叉树 H, 每个都有标准的顶点数 1 to 2^H-1。 根是 1 和孩子们 x 是 2 \cdot x 和 2 \cdot x + 1.
让 L 表示单棵树的叶子数量, L = 2^{H-1}.
给你一个排列 P_1, P_2, \ldots, P_L 数量 1 通过 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