配点 : 100 点
問題文
正整数 N 、素数 P ,长度 给出了 N 的 P 的正整数序列 A=(A_1,A_2,\dots,A_N) 。 如果输入
S=\lbrace 1,2,\dots,N\rbrace 。
满足以下所有条件的长度 大于或等于 1 的集合序列 T 的数量 P 的余数。
- T 的所有元素 S 的不为空 对于部分集合
- i=1,2,\dots,N ,以下情况成立
在
- T 的元素中, 包含i 的只是 A_i 個
制約
- 1\leq N\leq 2\times 10^5
- 113\leq P\leq 500009
- P 是素数
- 1\leq A_i\lt P (1\leq i\leq N)
- 输入全部为整数
入力
输入是按以下格式从标准输入给出的。
N P A_1 A_2 \dots A_N
出力
打印答案。 元素小于
入力例 1
2 113 1 2
出力例 1
5
T 是可能的 (\lbrace 1,2\rbrace,\lbrace 2\rbrace),(\lbrace 2\rbrace,\lbrace 1,2\rbrace),(\lbrace 1\rbrace,\lbrace 2\rbrace,\lbrace 2\rbrace),(\lbrace 2\rbrace,\lbrace 1\rbrace,\lbrace 2\rbrace),(\lbrace 2\rbrace,\lbrace 2\rbrace,\lbrace 1\rbrace) 的 5 没错。 不要忘记除以
入力例 2
4 8191 7 6 3 8
出力例 2
4477
T 的数量 P 来计算余数。