配点 : 1200 点
問題文
长度 小于或等于 N 整数序列 给出 A=(A_1,A_2,\ldots,A_N) 以及整数 K 被给出。 函数 f(L,R) (1 \leq L \leq R \leq N) 定义如下。
- R-L +1 < K 时,f(L,R)=0 。
- 否则,(A_L,A_{L+1},\ldots,A_{R}) 减去 K 考虑以不重叠的方式取出个非空连续子序列。 "最左边子序列中包含元素的总和的绝对值"+"其他子序列中包含元素的总和"可能达到的最大值 f(L,R) 为。 更形式地说,f(L,R)=\max_{L\leq l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_K \leq r_K \leq R}(|\sum_{l_1 \leq i \leq r_1} A_i| + \sum_{2 \leq j \leq K} \sum_{l_j \leq i \leq r_j} A_i) 。
\sum_{1 \leq L \leq R \leq N} f(L,R) 该值应乘以 998244353 求除以 的余数 (将负数求余数也 0 以上 998244353 在以下范围内求得)。
制約
- 1 \leq K \leq N \leq 250000
- K \leq 4
- -10^9 \leq A_i \leq 10^9
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N K A_1 A_2 \ldots A_N
出力
打印答案。
入力例 1
3 2 2 -2 -1
出力例 1
2
K \leq R-L+1 以同样的方式定义 f(L,R) 的值如下。 满足
- (L,R)=(1,2) 时: (l_1,r_1,l_2,r_2)=(1,1,2,2) 达到最大值的f(L,R)=0 变为。
- (L,R)=(1,3) 时: (l_1,r_1,l_2,r_2)=(1,1,3,3) 达到最大值的f(L,R)=1 变为。
- (L,R)=(2,3) 时: (l_1,r_1,l_2,r_2)=(2,2,3,3) 达到最大值的f(L,R)=1 变为。
因此,即它们的和 2 是答案。
入力例 2
5 2 -1 -2 -4 -8 -16
出力例 2
998244327
入力例 3
10 3 -21 -75 -29 -5 -99 -60 -75 -98 -48 -66
出力例 3
2320
入力例 4
15 4 -296045184 -17176032 -21940358 388585142 -410726492 244506160 -324910496 -99305133 -45869288 -25027474 -109128673 105493294 -6256129 -40956935 -33486703
出力例 4
51969020