题目背景

前置技能：线性递推 $\&~\rm BM$ 算法。

同时，请注意优化你的空间。保证最短递推式唯一。

出题人为强行二合一感到很抱歉，但是其实也是可以学习一下 $k^2 \log n$ 线性递推的——保证在 -O2 指令下可以过。

题目描述

给出一个数列 $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$。