105030 - 子数组之和

给你长度为 n 的数组 a,求所有连续子数组之和。例如有数组a={1,2,3},子数组为{1},{2},{3},{1,2},{2,3},{1,2,3},其和为1+2+3+3+5+6 = 20。

Input

第一行包含一个整数 n(1≤n≤10^5)代表数组长度; 第二行包含 n个整数表示数组a(0≤ai≤10^5)。

Output

对于每组数据输出一行,包含答案,由于答案可能很大,需要对 998244353 取模。

Examples

Input

3
1 2 3

Output

20
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题