Description

The personal charm of gyx is limitless.

At the kite festival, there are $N$ students ($1 \le N \le 10^6$). Each student has an interest level $c_i$ in gyx ($|c_i| \le 10^9$). Because gyx’s personality is very distinctive, no student has an interest level of $0$. For each student, gyx can befriend them as a "laotie". gyx’s happiness is the sum of the interest levels of all the classmates he has befriended as "laotie". gyx does not want to do anything that makes him sad, so if all classmates dislike him (i.e., their interest levels are negative), gyx will leave the festival immediately.

gyx may choose $k$ classmates to befriend ($1 \le k \le N$), but once the set is chosen, the befriending order must follow their original order.

Because there are so many people at the festival, gyx does not want to remember all "laotie" for too long. He remembers more about those befriended earlier, and they are harder to forget. The condition for gyx to forget someone is if and only if, among the "laotie" he still remembers, the current one is the most recently befriended.

However, since gyx wants to befriend more classmates with different personalities, he is willing to befriend each classmate at most once. Even after forgetting, he will not befriend them again.

After all the students chosen by gyx have been befriended, as time passes, gyx will gradually forget all of them in the same manner as above, until he has forgotten every "laotie" he befriended, and then sets off on a new journey.

Because different sequences of befriending and forgetting may lead to interesting situations, gyx wants to know, while ensuring his happiness is maximized by choosing whom to befriend (thus fixing the order to their original order), how many different sequences of befriending and forgetting are possible.

Because there are so many people at the festival, gyx only wants the number of different sequences modulo $P$ ($0 < P \le 10^9$).

Input Format

The first line contains two integers $N$ and $P$, representing the number of students at the festival and the modulus $P$ for the answer.

The next $N$ lines each contain one value $c_i$, representing the interest level of the $i$-th student in gyx.

Output Format

If everyone dislikes gyx, output Terrible Place.

Otherwise, output the number of different sequences modulo $P$.

8 65
-1
36
21
97
-65
17
1
43

2

Hint

For $30\%$ of the testdata: $1 \le N \le 30$.

For $70\%$ of the testdata: $1 \le N \le 500$.

For $100\%$ of the testdata: $1 \le N \le 10^6$, $0 < P \le 10^9$, $|c_i| \le 10^9$.

Translated by ChatGPT 5