Description

There are $n$ children standing in a line. Each child holds a number, which can be positive or negative. The characteristic value of a child is defined as the maximum possible sum of a contiguous block of one or more children among those standing in front of him (including himself).

As their teacher, you need to assign each child a score as follows: the first child's score equals his characteristic value. For any other child, his score equals the maximum, over all children standing before him (excluding himself), of the previous child's score plus his own characteristic value.

Please compute the maximum score among all children. When outputting, keep the sign of this maximum score, take its absolute value modulo $p$, and output the result with the sign kept.

Input Format

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

The second line contains $n$ integers, separated by spaces, representing the number held by each child.

Output Format

Output a single integer, which is the maximum score modulo $p$, with its sign preserved.

5 997
1 2 3 4 5

21

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

-1

Hint

Sample Explanation 1

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

Sample Explanation 2

The characteristic values of the children are $-1, -1, -1, -1, -1$, and the scores are $-1, -2, -2, -2, -2$. The maximum value is $-1$, and $-1 \bmod 7$ is $-1$, so output $-1$.

Constraints

For $50\%$ of the testdata, $1 \le n \le 1000$, $1 \le p \le 1000$, and the absolute value of every number does not exceed $1000$.

For $100\%$ of the testdata, $1 \le n \le {10}^6$, $1 \le p \le {10}^9$, and the absolute value of every other number does not exceed ${10}^9$.

Translated by ChatGPT 5