Description

一天，香港记者射命丸文从荷取那里购买了$n$张胶卷。而作为幻想乡的记者，文文对胶卷有着极其严格的要求。

她先对胶卷按顺序标号为$1-n$，并对第i张胶卷$（1\leq i\leq n）$ 附上本值 $h_i$ ，表示对该胶卷的初印象。之后文文对每张胶卷附上次值$z$，她对次值的定义是：“对于第$i$张胶卷$（2\leq i\leq n）$,满足次值$z_i$为在第 $1$张至第$i$张内连续几张胶卷的本值之和的最大值。第一张胶卷的次值即为该胶卷的本值。”最后文文每张胶卷附上文值$a$，对文值的定义是：“对于第$i$张胶卷$（2\leq i\leq n）$，满足文值$a_i$为第$1$张至第$i-1$张内的第$j$张胶卷的次值 $z_j$ 和文值$a_j$之和的最大值。第一张胶卷的文值即为该胶卷的本值。”文文对这 $n$ 张胶卷的最终评价值$ans$即为这$n$张胶卷中所有文值的最大文值。

由于该工作工作量较大，文文向你求助计算最终评价值$ans$。但最终评价值$ans$可能很大，所以文文会给你一个数$aya$，只需输出$ans \% aya$的结果。

Input Format

从$film.in$读入文件。

第一行包含两个正整数$n$和$aya$，之间用一个空格隔开。

第二行包含$n$个数，每两个整数之间用一个空格隔开，表示每张胶卷的本值。

Output Format

输出文件于$film.out$。

一个整数，表示$ans$对$aya$取模的结果。

Sample

样例输入1

5 123
4 3 5 1 2

样例输出1

40

样例输入2

5 7
-1 -1 -1 -1 -1

样例输出2

-1

解释(样例1)：胶卷的次值分别为$4,7,12,13,15$。文值分别为$4,8,15,27,40$。最终评价值$40$对$123$的模是$40$。

Hint

对于 $50\%$ 的数据，$1\leq n,aya \leq 10^3$,$0\leq |h_i| \leq 10^3$;

对于 $100\%$ 的数据，$1\leq n \leq 10^6$,$1\leq aya \leq 10^9$,$0\leq |h_i| \leq 10^9$。