题目背景

少女于海边伫立，凝视着落日最后的余晖
“已然过去了呢，旧历的一年......”

已获得转载授权。

题目描述

给定序列 $\{a_n\}$，满足每一项都不小于前一项。对于所有不超过 $k$ 的正整数 $m$，询问如果将 $a$ 分成 $m$ 段（可以有空段），并给从前往后第 $i$ 段内的每个数都加上 $i$，增加后的 $\sum\limits_{j=1}^n a_j^2$ 最大是多少。询问相互独立，即每次询问时给每个数加的值不保留到下一次询问。

例如，对于序列 $\{-3,1,2,2\}$，若 $m=5$，则一种分段方式是 $[-3][][1,2][][2]$，增加后的序列是 $-2,4,5,7$，此时 $\sum\limits_{j=1}^n a_j^2=94$。

记 $m=i$ 时的答案（即此时最大的 $\sum\limits_{j=1}^n a_j^2$）为 $q_i$，出于良心考虑，你只需要输出 $\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353$ 即可。标准程序不基于特殊的输出方式，即能独立求出每一个 $q_i$。

输入格式

第一行两个正整数 $n,k$，同题意。

接下来一行 $n$ 个整数，表示 $\{a_n\}$。

输出格式

一行一个整数，表示 $\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353$。

4 3
-3 1 2 2

141

提示

【样例解释】

当 $m=1$ 时，最优策略是 $[-3,1,2,2]$，$q_1=(-2)^2+2^2+3^2+3^2=26$。

当 $m=2$ 时，最优策略是 $[-3][1,2,2]$，$q_2=(-2)^2+3^2+4^2+4^2=45$。

当 $m=3$ 时，最优策略是 $[-3][][1,2,2]$，$q_3=(-2)^2+4^2+5^2+5^2=70$。

则 $\left(\sum\limits_{i=1}^k q_i\right) \bmod 998244353=(q_1+q_2+q_3)\bmod 998244353=(26+45+70)\bmod 998244353=141$。

【数据范围与约束】