旅游

题号：NC220738
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛在X城市旅游。X城市可以看成是一个 $2\times n$ 的网格图，图上的每个点是X城市的一个建筑物，每条边代表连接两个建筑物之间的道路。

我们把第一行的建筑物从左到右编号为 ${1}$ 到 ${n}$ ，第二行的建筑物从左到右编号为 ${n+1}$ 到 ${2n}$ 。
建筑物 ${i}$ 到建筑物 ${i+1}$ ( $1\leq i<n$ 或 $n+1\leq i< 2n$ )的道路长度为 ${1}$ 。
建筑物 ${i}$ 到建筑物 ${n+i}$ ( $1\leq i\leq n$ )的长度为 $a_i$ 。

现在牛牛在规划旅游的路线，牛牛会选择从建筑物 ${s}$ 出发 $(1\leq s < n)$ ，然后走到建筑物t结束 $(n+s < t \leq 2n)$ 。
因为牛牛不喜欢重复，所以一条合法的路线是从 ${s}$ 到 ${t}$ 的一条简单路径，即这条路径不能经过同一个点两次。

现在牛牛想知道，所有合法的路线的长度和为多少。一条路线的长度是这条路线上所有道路长度的和。答案模998244353。

输入描述:

第一行三个整数。。
第二行个整数。。

输出描述:

输出一行一个整数，整数要对998244353取模。

示例1

输入

复制

4 2 7
1 2 3 4

输出

复制

说明

2到7的合法路径有：
2->1->5->6->7，长度为4
2->3->4->8->7，长度为7
2->3->7，长度为4
2->6->7，长度为3
长度和为4+7+4+3=18

示例2

输入

复制

8 2 15
9 4 9 8 6 6 7 6

输出

复制