AT_waipc_qual_g Sum of Max of Sum of K Segments

長さ $ 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 $ 未満の範囲で求めてください）．

入力は以下の形式で標準入力から与えられる． > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

答えを出力せよ．

### Sample Explanation 1 $ 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 $ が答えです． ### Constraints - $ 1 \leq K \leq N \leq 250000 $ - $ K \leq 4 $ - $ -10^9 \leq A_i \leq 10^9 $ - 入力はすべて整数