#4233. [Cerc2013]Captain Obvious and the Rabbit-Man

内存限制:128 MiB 时间限制:10 Sec

题目描述

定义F:
F(1) = 1,
F(2) = 2,
F(n) = F(n-1) + F(n-2) (n >= 3)
定义p:
p(i) = a1*F(1)^i + a2*F(2)^i + … + ak*F(k)^i
其中k和a1…ak为常数。
现在已知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