Ball Arrangements and Chaos

You are given n types of balls, where for the i^th color there are a_i balls (balls of the same color are indistinguishable). For any interval of colors [l, r], define its chaos f(l, r) as the number of distinct arrangements when all balls of colors l to r are lined up, taken modulo p.

The number of arrangements, before taking modulo, is given by the multinomial coefficient:

[ f(l, r)=\frac{(a_l+a_{l+1}+\cdots+a_r)!}{a_l!,a_{l+1}!\cdots a_r!} \pmod{p} ]

Your task is to compute the following sum:

[ S=\sum_{l=1}^{n}\sum_{r=l}^{n} f(l, r) ]

Note that for each interval the arrangement count has been taken modulo p, and then these values are summed up (without any further modulo operation on the sum).

inputFormat

The first line contains two positive integers n and p (p is a prime number).

The second line contains n positive integers: a₁, a₂, ..., a_n, where a_i denotes the number of balls of the i^th color.

outputFormat

Output a single integer — the value of S defined above.

sample

2 7
1 1

3