Captain Obvious and Rabbit‐Man's Malicious Acts

In this problem, you are given a sequence defined by

\( F_1 = 1, \quad F_2 = 2, \quad F_n = F_{n-1} + F_{n-2} \text{ for } n \ge 3. \)

For a fixed positive integer \( k \), unknown integer coefficients \( a_1, a_2, \dots, a_k \) and a prime modulus \( M \) are chosen. The villain Rabbit‐Man performs his malicious acts on day \( i \) at a location labelled by

\( p(i) = a_{1} \cdot F_{1}^{i} + a_{2} \cdot F_{2}^{i} + \cdots + a_{k} \cdot F_{k}^{i} \) (mod \( M \)).

You are given \( k \) and the first \( k \) values \( p(1), p(2), \dots, p(k) \). It is guaranteed that the numbers \( F_1, F_2, \dots, F_k \) are pairwise distinct modulo \( M \) and that there is a unique solution. Your task is to compute \( p(k+1) \) modulo \( M \).

Hint: By writing the system of equations \[ \begin{aligned} p(1)&=a_1 F_1^1 + a_2 F_2^1 + \cdots + a_k F_k^1,\\ p(2)&=a_1 F_1^2 + a_2 F_2^2 + \cdots + a_k F_k^2,\\ &\ \vdots\\ p(k)&=a_1 F_1^k + a_2 F_2^k + \cdots + a_k F_k^k, \end{aligned} \] one may solve for the coefficients \( a_i \) using the Vandermonde matrix. An alternative approach is to note that the sequence \( p(i)\) satisfies a linear recurrence of order \( k \) with characteristic polynomial \[ \prod_{j=1}^{k}(x-F_j)=x^k - s_1 x^{k-1} + s_2 x^{k-2} - \cdots + (-1)^k s_k, \] where \( s_i \) is the \( i\)th elementary symmetric sum of \( F_1, F_2, \dots, F_k \). Multiplying the identity by \( a_j \) and summing over \( j \) leads to the recurrence

[ p(k+1)= s_1 p(k) - s_2 p(k-1) + \cdots + (-1)^{k-1} s_k p(1) \quad (\bmod\ M). ]

Use this recurrence to compute \( p(k+1) \) modulo \( M \).

inputFormat

The first line contains two integers \( k \) and \( M \) (where \( M \) is prime). The second line contains \( k \) space‐separated integers: \( p(1), p(2), \dots, p(k) \), given modulo \( M \).

outputFormat

Output a single integer: \( p(k+1) \) modulo \( M \).

sample

2 1000003
11 19

35