[AdditionalFile5535.zip](file://AdditionalFile5535.zip?type=additional_file)

#5535. 「PA 2018 Final」Sznurowadła

标签: 传统 | 时间限制: 4000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2018 Final Sznurowadła

几乎每个想到绝妙商业想法的人，首先考虑的是潜在的巨大利润。然而，这并不是最重要的。Bitomir 意识到成功的关键在于最小化和估算成本。他计划从事鞋带贸易，因为在 Cajtocja 突然对鞋带的需求激增。鞋带在 Aajtocja 生产，因此必须通过位于两者之间的 Bajtocja 运输。

Bajtocja 由 $n$ 个区域组成，编号从 $1$ 到 $n$，每个区域有两座城市。对于每个 $i$ $(1 \leq i \leq 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 \ldots \cdot a_{n-1}^{4}$ 种可能的场景，即每条道路的税额可能情况。为了计算平均预期运输成本，Bitomir 开始计算所有场景下运输成本的总和。不幸的是，疲劳占了上风，Bitomir 陷入了梦乡。你能替他计算这个总和吗？输出结果对 $2^{32}$ 取模的值。

输入格式

输入的第一行包含一个整数 $n$ $(2 \leq n \leq 8)$，表示 Bajtocja 的区域数量。

第二行包含 $n-1$ 个整数 $a_{1}, a_{2}, \ldots, a_{n-1}$ $(1 \leq a_{i} \leq 3000)$，表示每个区域的最大可能税额。

输出格式

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

样例 1

输入

2
2

输出

17

在第一个样例中，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

输出

78784

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