#P18750. [正睿NOI2021训练] 最短路
[正睿NOI2021训练] 最短路
最短路
有一个 个节点的有向图:除源点 、汇点 外,有 列,每列两个节点,记为 。
- 分别连向 ,边权都是 。
- 分别连向 ,边权都是 。
- 对每个 ,从 分别向 连边,共四条。每条边的权值都可以独立取 中的任意整数。
对所有可能的内部边权赋值方案,分别计算 到 的最短路长度,求这些长度的总和,对 取模。
这里求的是总和,不是期望。一个方案中,同一列间的四条边的权值不要求相同。
输入格式
第一行一个正整数 。
第二行 个正整数 。 时没有这些整数。
输出格式
输出一个整数,表示总和模 后的非负余数,范围为 。
数据范围
,。
样例 1
输入
2
3
输出
98
样例 2
输入
4
2 3 3
输出
395347