← 返回题目列表

AtCoder · pakencamp_2025_day3_j

J. 设置顺序

中文机器翻译题面 查看原题

配点 : 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 来计算余数。