[Wind Festival]Finding RhFe

题目背景

$[Morning - 8:00 A.M.]$ 热衷于结交老铁的$gyx$小哥哥听说了风筝节的举办,一大早就来到了现场,现在他已经迫不及待见到来玩的同学们啦~

题目描述

$gyx$的人格魅力是无限哒~ 已知风筝节上有$N$($1\le N\le 10^6$)个同学(来玩的人真的很多),每个同学都对$gyx$有一个兴趣程度$c_i$($ |c_i|\le 10^9$),因为$gyx$的性格特点太明显啦,不存在对$gyx$兴趣程度为$0$的同学,对于每个同学,都可以和$gyx$结交为老铁,$gyx$的高兴程度就是所有结!交!过!成为老铁的同学对$gyx$兴趣程度之和。$gyx$不愿意做令自己伤心的事情,所以如果所有同学对$gyx$感到反感(即兴趣程度为负)$gyx$就会直接离开风筝节。 $gyx$可以选择其中的$k$($1\le k\le N$)个同学来结交,但一旦选择好,$gyx$的结交顺序就不可以变化了。 因为来风筝节的人实在是太多啦,$gyx$不愿意记住所有的老铁太长的时间,但是$gyx$的脑子里记着与越早结交的老铁的点点滴滴越多,也越难忘记,$gyx$忘记每个人的条件是当且仅当,在$gyx$还记着的老铁里当前的这个老铁是最后结交的。 但是由于$gyx$希望与更多不同性格的同学结交,$gyx$与每一个同学只愿意结交一次,即使遗忘以后也不会再次结交。 当风筝节上$gyx$选择的同学都结交结束后,随着时间的流逝,$gyx$也会渐渐地把所有同学都忘掉,遗忘方式与之前相同,直到最后忘记了自己结交过的所有老铁,再出发前往新的征程。 由于不同的交友并遗忘的顺序可能会发生有趣的事情,$gyx$想知道在保证自己高兴程度最大时选择好结交范围和结交顺序的情况下,$gyx$可以有多少种不同的交友并遗忘的顺序呢? 由于来风筝节的人实在是太多了,$gyx$只想知道不同顺序的方案数的值对$P$($0<P\le 10^9$)取模后的结果。

输入输出格式

输入格式


第一行是两个数$N$和$P$,分别表示来风筝节的同学人数和方案数要对P取模; 接下来的$N$行每行一个$c_i$的值,表示第$i$个同学对$gyx$的兴趣程度;

输出格式


如果所有人对$gyx$都感到讨厌输出“$Terrible Place$”; 其他情况输出对$P$取模后不同的顺序的方案数的值;

输入输出样例

输入样例 #1

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

输出样例 #1

2

说明

对于$30\%$的数据保证$1\le N\le 30$; 对于$70\%$的数据保证$1\le N\le 500$; 对于$100\%$的数据保证$1\le N\le 10^6$,$0<P\le 10^9$,$|c_i|\le 10^9$。