说明

给出一个数列 $P$ 从 $0$ 开始的前 $n$ 项。

求序列 $P$ 在 $\bmod~998244353$ 下的最短线性递推式，并在 $\bmod~998244353$ 下输出 $P_m$。

输入格式

第一行共两个数 $n,m$ ，表示将会给出序列 $P$ 的前 $n$ 项，要求 $P_m$。

第二行 $n$ 个数，表示 $P_0,P_1,P_2,\ldots,P_{n-1}$。

输出格式

第一行输出该最短线性递推式。

第二行输出 $P_m$ 的值。

4 10
1 1 2 3

1 1 
89

5 10
3 7 27 95 339

3 2
691707

提示

对于 $100 \%$ 的数据，$n < m \le {10}^9$，$1 \le n \le 10000$，保证递推式最长不超过 $5000$。