Berland 国王再次举办了一场击剑锦标赛。来自全国各地的共 $2^k$ 名顶尖选手齐聚 Berland 首都，为了荣誉，当然也为了丰厚的奖金而战。

每位选手根据其实力被赋予一个介于 $1$ 到 $2^k$ 之间的编号：最强的选手编号为 $1$，次强的选手编号为 $2$，依此类推，最弱的选手编号为 $2^k$。比赛采用标准的淘汰赛制：选手们被随机分配到锦标赛对阵表（一棵拥有 $2^k$ 个叶子的满二叉树）的叶子节点上。所有初始排列方案都是等概率的。然后，在对阵表中拥有相同父节点的每对选手之间进行比赛，胜者晋级下一轮，败者被淘汰。这个过程一直持续到只剩下一位选手。显而易见，所有比赛的参赛者和结果都由初始排列唯一确定。

事实上，比赛毫无悬念：编号较小的选手总是能战胜编号较大的选手。尽管如此，比赛依然具有观赏性，而且某些选手的比赛比其他选手的更有趣。具体来说，第 $i$ 位选手有一个娱乐度 $a_i$；请注意，有些选手可能不是最强的，但他们的比赛却很有趣，这意味着 $a_i$ 的大小与 $i$ 的大小没有任何关联。如果编号为 $i$ 和 $j$ 的选手进行一场比赛，该场比赛的精彩度为 $a_i \cdot a_j$。整个锦标赛的娱乐度定义为所有进行的比赛的精彩度之和。

门票的销量（从而也就是赚到的钱数）很大程度上取决于比赛的精彩度。目前种子排位（初始排列）尚未公布，国王要求你计算整个锦标赛娱乐度的期望值。请注意，由于所有比赛的结果都是预先确定的，因此该期望值仅取决于随机的初始排列。

输入格式

第一行包含唯一的整数 $k$ ($1 \le k \le 18$) —— 锦标赛的轮数。

第二行包含 $2^k$ 个空格分隔的整数 $a_1, \dots, a_{2^k}$ ($0 \le a_i \le 10^9$) —— 选手的娱乐度。

输出格式

设所有比赛的总精彩度期望值为最简分数 $P/Q$。输出 $P \cdot Q^{-1}$ 在模 $1\,000\,000\,007$ ($10^9 + 7$) 的素域中的值。保证该模数不能整除 $Q$，因此待求的输出值是唯一确定的。

样例

样例输入 1

1
2 3

样例输出 1

6

样例输入 2

2
1 2 3 4

样例输出 2

14

样例输入 3

2
4 3 2 1

样例输出 3

333333358

说明

在第三个样例中，期望值为 $\frac{67}{3}$。