Gyx's Maximum Happiness

Gyx has an infinite personality charm. At the kite festival, there are (N) students, each with an interest level (c_i) towards Gyx, where (|c_i| \le 10^9) and (c_i \neq 0). Gyx’s happiness is defined as the sum of the interest levels of the students he eventually befriends. However, if every student dislikes him (i.e. each (c_i < 0)), Gyx will directly leave the festival.

Gyx can choose exactly (k) students ((1 \le k \le N)) to befriend, and once chosen, their order of befriending is fixed. After all friendships are made, as time passes, Gyx forgets all his friends gradually following the rule: at any moment, he forgets a friend if and only if that friend is the most recently befriended among those he still remembers. Note that Gyx never befriends the same student twice, even if he has forgotten them.

To maximize his happiness, Gyx should only befriend the students with a positive interest level. Let (k) be the number of students with (c_i > 0). The number of different sequences of befriending (which can be arranged in (k!) orders) combined with the forced forgetting process (which is the reverse of the befriending order) is (k!). Since the answer can be very large, output the result modulo (P) (,(0 < P \le 10^9)).

If there are no students with a positive interest level, output 0.

inputFormat

The first line contains two integers \(N\) and \(P\), where \(1 \le N \le 10^6\) and \(0 < P \le 10^9\).

The second line contains \(N\) integers \(c_1, c_2, \dots, c_N\) (\(|c_i| \le 10^9\) and \(c_i \neq 0\)), representing the interest levels of the students.

outputFormat

Output a single integer representing the number of different befriending and forgetting sequences that yield maximum happiness (i.e. \(k!\) modulo \(P\)), where \(k\) is the number of students with positive interest levels. If no student has a positive interest level, output 0.

sample

5 100
1 2 -3 4 -5

6