Description

B君有一个长度为 $n$ 的数列 $A_i$，接下来他会对这个数列做如下的魔法:

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

例如，设 $n = 4, K = 10, A = \{ 7, 2, 8, 5 \}$，过程如下：

$7\ 2\ 8\ 5$

$9\ 0\ 3$

$9\ 3$

$2$

现在对于给定的数列 $A_i$，请你求出B君对它施展魔法后，最后剩下的那个数是多少。

Input Format

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

第二行 $n$ 个非负整数表示数列 $A_i$

Output Format

仅一行一个整数表示答案

Sample

样例输入

4 10
7 2 8 5

样例输出

2

Hint

$20 \%$ 的数据，$n \leq 1000$

另有 $20 \%$ 的数据，$K$ 是质数

另有 $30 \%$ 的数据，$K = 10$

$100 \%$ 的数据，$ 1 \leq n \leq 4 \times 10 ^ 5, 1 \leq K \leq 10 ^6, 0 \leq A_i \leq K $