Problem Background

Prerequisite Skills: Linear Recurrence & BM Algorithm.

Please also optimize your space usage. Ensure that the shortest recurrence formula is unique.

The problem setter apologizes for the forced combination of two topics, but it is also an opportunity to learn about the $k^2 \log n$ linear recurrence—guaranteed to pass under -O2 optimization.

Problem Description

Given a sequence $P$ from the first $n$ terms starting from $0$.

Find the shortest linear recurrence formula of sequence $P$ under $\bmod~998244353$, and output $P_m$ under $\bmod~998244353$.

Input and Output Format

Input Format

The first line contains two numbers $n, m$, indicating the first $n$ terms of sequence $P$ and the requirement for $P_m$.

The second line contains $n$ numbers, representing $P_0, P_1, P_2, \ldots, P_{n-1}$.

Output Format

The first line outputs the shortest linear recurrence formula.

The second line outputs the value of $P_m$.

Sample Input and Output

Sample Input #1

4 10
1 1 2 3

Sample Output #1

1 1
89

Sample Input #2

5 10
3 7 27 95 339

Sample Output #2

3 2
691707

Notes

For $100\%$ of the data, $n < m \leq 10^9$, $1 \leq n \leq 10000$, and the length of the recurrence formula does not exceed $5000$.

见题面 Input 部分

见题面 Output 部分