几乎每个想到绝妙商业点子的人，首先想到的都是潜在的巨额利润。但这不是最重要的。Bitomir 意识到，成功的关键在于最小化并估算成本。他计划从事鞋带贸易，因为 Cajtocja 对鞋带的需求突然激增。鞋带在 Aajtocja 生产，因此必须经过位于中间的 Bajtocja 进行运输。

Bajtocja 由 $n$ 个区域组成，编号从 $1$ 到 $n$，每个区域有两个城市。对于每个 $i$ ($1 \le i \le n - 1$)，从区域 $i$ 中的每个城市到区域 $i + 1$ 中的每个城市都有一条有向道路，其关税为区间 $[1, a_i]$ 内的一个整数，其中 $a_i$ 是由区域 $i$ 的管理部门设定的上限。Bitomir 很久没去过 Bajtocja 了，不知道每条道路的具体关税，但他知道 $a_i$ 的值。

Bitomir 需要进入 Bajtocja 第一个区域的某个城市，到达第 $n$ 个区域，然后离开 Bajtocja，以便在 Cajtocja 出售他的货物。在穿过 Bajtocja 时，Bitomir 当然会选择一条关税总和最小的道路序列，该总和即为运输成本。

晚上躺在床上时，Bitomir 考虑了 $a_1^4 \cdot a_2^4 \cdot \dots \cdot a_{n-1}^4$ 种可能出现的关税场景。为了计算预期的平均运输成本，Bitomir 开始计算所有场景下的运输成本之和。不幸的是，疲劳战胜了他，Bitomir 沉沉睡去。你能帮他计算这个总和吗？请输出结果对 $2^{32}$ 取模的值。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 8$)，表示 Bajtocja 的区域数量。 第二行包含 $n - 1$ 个整数 $a_1, a_2, \dots, a_{n-1}$ ($1 \le a_i \le 3000$)，表示每个区域的关税上限。

输出格式

输出一个整数，表示所有场景下运输成本的总和，对 $2^{32}$ 取模。

样例

样例输入 1

2
2

样例输出 1

17

说明 1

在第一个测试中，Bajtocja 有 $n = 2$ 个区域。Bitomir 想从第一个区域到达第二个区域，他有四条有向道路可供选择，每条道路的关税为 $1$ 或 $2$（因为 $a_1 = 2$）。如果所有道路的关税都是 $2$，Bitomir 会选择任意一条道路，运输成本为 $2$。在其余 $15$ 种场景中，至少存在一条关税为 $1$ 的道路，因此运输成本为 $1$。结果为 $1 \cdot 2 + 15 \cdot 1 = 17$。

样例输入 2

4
3 4 1

样例输出 2

78784

说明 2

在第二个测试中，我们有 $n = 4$ 个区域。下图展示了 Bajtocja 的布局。带有数字 $i$ 的圆圈表示第 $i$ 个区域中的城市。图中还标出了 Aajtocja（从中进入第一个区域）和 Cajtocja，但只有 Bajtocja 各区域之间的道路有关税。图中还展示了一个道路关税分布的示例，其中加粗的路径为最优路径，其运输成本为 $1 + 2 + 1 = 4$。