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 $ について、以下が成り立つ - $ T $ の要素のうち、 $ i $ を含むものはちょうど $ A_i $ 個

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを出力せよ。

### Sample Explanation 1 $ 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 $ 通りです。 ### Sample Explanation 2 $ T $ の個数を $ P $ で割った余りで求めることを忘れないでください。 ### Constraints - $ 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) $ - 入力はすべて整数