题目描述

众所周知，斐波那契数列的公式如下：

$$F_i=\begin{cases}1&i=1\\2&i=2\\F_{i-1}+F_{i-2}&i\geqslant 3\end{cases} $$

定义 $p_i=\sum\limits_{j=1}^ka_j\times F_j^i$。现在给定 $k,m$ 以及 $\{p_i\}_{i=1}^k$，请求出 $p_{k+1}\bmod m$。

为了避免高精度，所有运算都模掉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 \le k \le 4000 , 3 \le M \le 10^{9}.$

题目来源

没有写明来源