5.魔法操作

题目描述

小明有一个长度为 $n$ 的数列 $A_{i}$ ，接下来他会对这个数列做如下的魔法：

若当前数列长度为 $m$ ，小明会将数列中所有相邻的数相加并 $\bmod p$ ，之后将这依次得到的 $m-1$ 个数，按照原顺序排成新的数列。小明会不停重复该操作，直到该数列只剩下一个数为止。

例如，设 $n=4$ ， $p=10$ ， $A=7,2,8,5$ ，过程如下：

$7$ $2$ $8$ $5$

$9$ $0$ $3$

$9$ $3$

$2$

现在对于给定的数列 $A_{i}$ ，请你求出小明对它施展魔法后，最后剩下的那个数是多少。

第一行两个正整数 $n$ ， $p$ ，意义见题目描述。

第二行 $n$ 个非负整数表示数列 $A_{i}$ 。

仅一行一个整数表示答案。

对于 $20\%$ 的数据，满足 $n < 1000$ ；
另有 $20\%$ 的数据，满足 $p$ 是质数；
另有 $30\%$ 的数据，满足 $p = 10$ ；
对于 $100\%$ 的数据，满足 $1 \leq n \leq 4 \times 10^{5}$ ， $1 \leq p \leq 10^{6}$ ， $0 \leq A_{i} < p$ 。

4 10
7 2 8 5