#P18032. Set Sequence

Set Sequence

Set Sequence

给定正整数 NN、素数 PP,以及长度为 NN 的整数序列 AA。

求满足以下条件的序列 (S1,S2,…,Sm)(S_1,S_2,\ldots,S_m) 的数量,对 PP 取模:

  • m≥1m\ge1;
  • 每个 SjS_j 都是 {1,2,…,N}\{1,2,\ldots,N\} 的非空子集;
  • 对每个 ii,恰好有 AiA_i 个集合 SjS_j 包含 ii。

集合内部没有顺序,但序列中集合的位置有顺序。同一个集合可以在不同位置重复出现。

输入格式

第一行两个整数 N,PN,P。第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。

输出格式

输出一个整数,表示满足条件的序列数量对 PP 取模的结果。

数据范围

1≤N≤2×1051\le N\le2\times10^5,113≤P≤500009113\le P\le500009,保证 PP 为素数,1≤Ai≤P−11\le A_i\le P-1。所有输入均为整数。

样例 1

输入:

2 113
1 2

输出:

5

样例 2

输入:

4 8191
7 6 3 8

输出:

4477