题目描述
小明有一个长度为 $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`
现在对于给定的数列 $n$，请你求出小明对它施展魔法后，最后剩下的那个数是多少。
输入
第一行两个正整数 $n,p$，意义见题目描述。
第二行 $n$ 个非负整数表示数列 $A_i$。
输出
仅一行一个整数表示答案。
样例输入输出
提示
对于 $20\%$ 的数据，满足 $n \leq 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$。