Description

You are given the first $n$ terms of a sequence $P$ starting from index $0$.

Find the shortest linear recurrence of sequence $P$ modulo $998244353$, and output $P_m$ modulo $998244353$.

Input Format

The first line contains two integers $n,m$, meaning that the first $n$ terms of sequence $P$ will be given, and you need to compute $P_m$.

The second line contains $n$ integers, which are $P_0,P_1,P_2,\ldots,P_{n-1}$.

Output Format

On the first line, output the shortest linear recurrence.

On the second line, output the value of $P_m$.

4 10
1 1 2 3

1 1 
89

5 10
3 7 27 95 339

3 2
691707

Hint

For $100\%$ of the testdata, $n < m \le 10^9$, $1 \le n \le 10000$, and the length of the recurrence is guaranteed to be at most $5000$.

Translated by ChatGPT 5