时间限制：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、10、70、140、140，最大值140 对 103 的模是 37。

【输入输出样例2】

　Input

6 11
-2 -3 1 -2 -1

　Output

-1

【输入输出样例2说明】

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

【数据说明】

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

【来源】

　　Mr.he