【模板】Berlekamp–Massey 算法
题目背景
前置技能：线性递推 $\&~\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$ 的值。
输入输出样例
输入样例 #1
4 10
1 1 2 3
输出样例 #1
1 1
89
输入样例 #2
5 10
3 7 27 95 339输出样例 #2
3 2
691707
说明
对于 $100 \%$ 的数据，$n < m \le {10}^9$，$1 \le n \le 10000$，保证递推式最长不超过 $5000$。