AT_pakencamp_2025_day3_j Set Sequence

给定正整数 $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$，恰好有 $A_i$ 个 $T$ 的元素包含 $i$。

输入以如下格式通过标准输入给出。 > $N\ P\ A_1\ A_2\ \dots\ A_N$

请输出答案。

### 样例解释 1 可能的 $T$ 有 $5$ 种，分别为 $(\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)$。 ### 样例解释 2 不要忘了对 $P$ 取余后输出 $T$ 的个数。 ### 数据范围 - $1\leq N\leq 2\times 10^5$ - $113\leq P\leq 500009$ - $P$ 是素数 - $1\leq A_i