Minimal Linear Recurrence and Sequence Term Computation

Given a sequence P starting from index 0 and containing the first n terms, determine the minimal (shortest) homogeneous linear recurrence relation that generates this sequence modulo \(998244353\). Using this recurrence relation, compute and output the value of P_m modulo \(998244353\).

The recurrence relation is of the form:

[ P(n) = c_1 \cdot P(n-1) + c_2 \cdot P(n-2) + \cdots + c_L \cdot P(n-L),\quad \text{for } n \ge L, ]

where the coefficients \(c_1, c_2, \dots, c_L\) (with \(L\) being minimal) are determined from the given first n terms of P. If \(m < n\), simply output the given \(P_m\).

Note: All computations should be performed modulo \(998244353\), and any formulas must be written in \(\LaTeX\) format.

inputFormat

The first line contains two integers n and m (1 \le n \le 10^5 and 0 \le m \le 10^18).

The second line contains n space‐separated integers representing the first n terms of the sequence P (\(P_0, P_1, \dots, P_{n-1}\)).

outputFormat

Output a single integer, which is \(P_m\) modulo \(998244353\).

sample

5 7
1 1 2 3 5

13