Background

Prerequisite skills: linear recurrence and the $\&~\rm BM$ algorithm.

Also, please pay attention to optimizing your memory usage. The shortest recurrence is guaranteed to be unique.

The problem setter apologizes for forcing two tasks into one, but this is also a chance to learn the $k^2 \log n$ method for linear recurrences. It is guaranteed to pass under the -O2 option.

Problem 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