Children's Scores with Feature Values

There are \( n \) children standing in a line. Each child holds a number (which can be positive or negative). For each child, define its feature value as the maximum sum of any contiguous segment (with at least one number) among the children standing before and including that child. In other words, for the \( i\)-th child the feature value is:

\[ \text{feature}[i] = \max_{1 \leq j \leq i} \left\{ \sum_{k=j}^{i'} a_k \right\} \] where the contiguous segment can be chosen arbitrarily among the children in positions \( 1 \) to \( i \) (note that \( i' \) is chosen so that the segment is within \( [1,i] \)).

The teacher assigns a score to each child in the following manner. The score of the first child is its feature value, that is,

\[ \text{score}[1] = \text{feature}[1]. \]

For every other child (i.e. for \( i \ge 2 \)), the score is defined as the sum of the maximum score among all children before it (i.e. children \( 1 \) to \( i-1 \)) and its own feature value:

\[ \text{score}[i] = \max_{1 \leq j < i} \{ \text{score}[j] \} + \text{feature}[i]. \]

Your task is to compute the maximum score among all children. Finally, output the result in a special format: keep the sign of the maximum score, but reduce its absolute value modulo \( p \). That is, if \( M \) is the maximum score, then the output should be

\[ \text{answer} = \begin{cases} M \bmod p, & \text{if } M \ge 0,\\ -\left(|M| \bmod p\right), & \text{if } M < 0. \end{cases} \]

inputFormat

The input consists of two lines:

• The first line contains two integers \( n \) and \( p \), where \( n \) is the number of children and \( p \) is the modulus.
• The second line contains \( n \) integers, representing the number held by each child.

outputFormat

Output a single integer: the maximum score among all children. The result should retain its sign, and its absolute value should be taken modulo \( p \).

sample

3 100
1 2 3

6