#P18750. [正睿NOI2021训练] 最短路

[正睿NOI2021训练] 最短路

最短路

有一个 2n+22n+2 个节点的有向图:除源点 ss、汇点 tt 外,有 nn 列,每列两个节点,记为 ui,viu_i,v_i。

  • ss 分别连向 u1,v1u_1,v_1,边权都是 00。
  • un,vnu_n,v_n 分别连向 tt,边权都是 00。
  • 对每个 1≤i<n1\le i<n,从 ui,viu_i,v_i 分别向 ui+1,vi+1u_{i+1},v_{i+1} 连边,共四条。每条边的权值都可以独立取 [1,ai][1,a_i] 中的任意整数。

对所有可能的内部边权赋值方案,分别计算 ss 到 tt 的最短路长度,求这些长度的总和,对 2322^{32} 取模。

这里求的是总和,不是期望。一个方案中,同一列间的四条边的权值不要求相同。

输入格式

第一行一个正整数 nn。

第二行 n−1n-1 个正整数 a1,…,an−1a_1,\ldots,a_{n-1}。n=1n=1 时没有这些整数。

输出格式

输出一个整数,表示总和模 2322^{32} 后的非负余数,范围为 [0,232−1][0,2^{32}-1]。

数据范围

1≤n≤20001\le n\le2000,1≤ai≤20001\le a_i\le2000。

样例 1

输入

2
3

输出

98

样例 2

输入

4
2 3 3

输出

395347