题目背景

T5 的第一句话是假的。

题目描述

注意，本题中下标从 $0$ 开始。

一个长度为 $n$ 的序列 $\{a_i\}$ 的权值 $v(a)$ 定义为：

• $n=1$ 时为 $v(a)=a_0$。
• $n>1$ 时为它所有子区间的权值之和，也就是 $v(a_0,a_1,\ldots,a_{n-1})=\sum\limits_{i=0}^{n-2}\sum\limits_{j=0}^{n-i-1}v(a_j,a_{j+1},\ldots,a_{j+i})$.

给定一个序列，求出它的的权值，答案对 $998244353$ 取模。

这个序列是这样生成的：输入序列 $b_0,b_1,\cdots,b_{k-1}$，然后 $a_i=b_{i\bmod k}$。

输入格式

第一行为 $n,k$，表示序列 $a$ 的长和序列 $b$ 的长。

第二行为 $b_0,b_1,\cdots,b_{k-1}$，含义见题目描述。

输出格式

一行一个整数，表示序列 $a$ 的权值对 $998244353$ 取余的结果。

4 3
3 4 6

104

10 10
2 5 3 8 4 5 2 19 3 6

219856

提示

【样例解释 #1】

生成序列 $a=[3,4,6,3]$，然后：

• $v(3,4)=v(3)+v(4)=7$
• $v(4,6)=v(4)+v(6)=10$
• $v(6,3)=v(6)+v(3)=9$
• $v(3,4,6)=v(3)+v(4)+v(6)+v(3,4)+v(4,6)=30$
• $v(4,6,3)=v(4)+v(6)+v(3)+v(4,6)+v(6,3)=32$
• $v(3,4,6,3)=v(3)+v(4)+v(6)+v(3)+v(3,4)+v(4,6)+v(6,3)+v(3,4,6)+v(4,6,3)=104$

【数据规模与约定】

本题不使用捆绑测试。

本题共 $25$ 个测试点，每个测试点 $4$ 分。

对于 $100\%$ 的数据 : $1\le n\le 10^9$，$1 \le k \le 10^5$，$0\le a_i\le 998244352$。

感谢 $\rm\textcolor{black}{J}\textcolor{red}{ohnVictor}$ 对此题的贡献。