题目描述

定义$F$： $F(1) = 1$, $F(2) = 2$, $F(n) = F(n-1) + F(n-2) (n \geq 3)$ 定义$p$： $p(i) = a_1 \times F(1)^i + a_2 \times F(2)^i + … + a_k \times F(k)^i$ 其中$k$和$a_1 \dots a_k$为常数。

现在已知$k$,$p(1),p(2),…,p(k)$，求$p(k+1)$。

为了避免高精度，所有运算都模掉$M$。

保证$F(1),…,F(n)$在模质数$M$下两两不同，保证有唯一解。

输入

第一行，两个整数$k,M$。 第二行，$p(1), p(2), . . . , p(k)$ 模$M$ 。

输出

输出$p(k+1)$模$M$。$M$为质数

样例输入

3 101
5 11 29

样例输出

83

提示

对于100%的数据，1<=k<=4000， 3<=M<=10^9