問題文

長さ 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
• 入力はすべて整数

入力例 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