Problem Background

NOIP2013 Junior Group T3

Problem Description

There are $n$ children standing in a line. Each child holds a number, which can be positive or negative. The characteristic value of each child is defined as the maximum sum of the numbers held by any contiguous group of children in front of them (including themselves).

As the teacher of these children, you need to assign a score to each child. The score is determined as follows: the first child's score is their characteristic value, and the score of each subsequent child is the maximum sum of the scores and characteristic values of all children in front of them (excluding themselves).

Calculate the maximum score among all children and output it, maintaining its sign and taking the absolute value modulo $p$.

Input Format

The first line contains two positive integers $n$ and $p$, separated by a space.

The second line contains $n$ integers, each separated by a space, representing the numbers held by each child.

Output Format

A single integer representing the maximum score modulo $p$.

Sample Input and Output

Sample Input #1

5 997
1 2 3 4 5

Sample Output #1

21

Sample Input #2

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

Sample Output #2

-1

Notes

Sample Explanation 1

The characteristic values of the children are $1, 3, 6, 10, 15$, and their scores are $1, 2, 5, 11, 21$. The maximum score $21$ modulo $997$ is $21$.

Sample Explanation 2

The characteristic values of the children are $-1, -1, -1, -1, -1$, and their scores are $-1, -2, -2, -2, -2$. The maximum score $-1$ modulo $7$ is $-1$, so the output is $-1$.

Data Range

For $50\%$ of the data, $1 \le n \le 1000$, $1 \le p \le 1000$, and the absolute values of all numbers do not exceed $1000$.

For $100\%$ of the data, $1 \le n \le 10^6$, $1 \le p \le 10^9$, and the absolute values of all other numbers do not exceed $10^9$.

见题面 Input 部分

见题面 Output 部分