测试数据来自 system/3054

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给定一个长度为 \(n\) 整数序列，然后给出如下定义：

　　1、特征值：第i个整数的特征值为前i个数中连续若干个（最少有一个）整数之和的最大值。

　　2、分数：序列的第一个整数的分数就是其特征值；而第i（i>1）整数的分数为他之前的i-1个数中，每个数的特征值与其分数和的最大值。

　　理解上面两个定义后，请你序列中分数的最大值，输出时保持最大值的符号，将其绝对值对 \(m\) 取模后输出。

【输入格式】

　　第一行包含两个正整数 \(n、m\)，意义如题目描述。
　　第二行包含 \(n\) 个数，表示给定的整数序列。
每行的相邻整数之间用一个空格隔开。

【输出格式】

　　输出一个整数，表示答案。

【输入输出样例1】

　Input

5 103
10 30 50 20 40 

　Output

21

【输入输出样例1说明】

　　每个整数的特征特征值分别为 10、40、90、110、150，分数分别为 10、20、60、150、260，最大值 260 对 103 的模是 54。

【输入输出样例2】

　Input

6 11
-2 -3 1 -2 -1 3

　Output

-1

【输入输出样例2说明】

　　每个整数的特征值为 -2 -2 1 1 1 3，分数分别为 -1 -4 -4 -3 -2 -1，最大值 -2 对 11 的模为 -2，输出 -2。

【数据说明】

　　对于 \(100\%\) 的数据，\(1 ≤ n ≤ 1,000,000， 1 ≤ m ≤ 10^9\)，所有数字的绝对值不超过 \(10^9\)。

【来源】

　　Mr.he