给你一个正整数 $N$、一个质数 $P$ 以及一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$，其中每个元素都小于 $P$。设 $S = \{1, 2, \dots, N\}$。

求满足以下所有条件的、长度至少为 1 的集合序列 $T$ 的数量，并将结果对 $P$ 取模后输出。

• $T$ 的每个元素都是 $S$ 的非空子集。
• 对于每个 $i = 1, 2, \dots, N$，满足以下条件：
  • 在 $T$ 的元素中，恰好有 $A_i$ 个包含 $i$。

输入格式

输入格式如下：

N P
A_1 A_2 ... A_N

数据范围

• $1 \le N \le 2 \times 10^5$
• $113 \le P \le 500009$
• $P$ 是一个质数
• $1 \le A_i < P$ ($1 \le i \le N$)
• 所有输入值均为整数

输出格式

输出答案。

样例

输入样例 1

2 113
1 2

输出样例 1

5

输入样例 2

4 8191
7 6 3 8

输出样例 2

4477

说明

对于第一个样例，可能的序列 $T$ 为 $(\{1, 2\}, \{2\})$、$(\{2\}, \{1, 2\})$、$(\{1\}, \{2\}, \{2\})$、$(\{2\}, \{1\}, \{2\})$、$(\{2\}, \{2\}, \{1\})$，共 5 个。

对于第二个样例，不要忘记求出满足条件的序列 $T$ 的数量对 $P$ 取模后的结果。