UOJ Logo

NOI.AC

1S 512MB

#1575. Captain obvious and the Rabbit-Man

Statistics

题目描述

定义$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