AT_abc425_e [ABC425E] Count Sequences 2

正整数 $ N $ および長さ $ N $ の正整数列 $ C=(C_1,C_2,\ldots,C_N) $ が与えられます。 次の条件をすべて満たす正整数列の個数を与えられた正整数 $ M $ で割った余りを求めてください。 - 数列の要素はすべて $ 1 $ 以上 $ N $ 以下である。 - 各 $ i=1,2,\ldots,N $ に対し、 $ i $ は数列にちょうど $ C_i $ 個含まれる。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。ただし、 $ M $ は $ T $ 個すべてのテストケースにおいて共通です。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ M $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ $ i $ 番目のテストケース $ \mathrm{case}_i $ は以下の形式で与えられる。 > $ N $ $ C_1 $ $ C_2 $ $ \ldots $ $ C_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、条件を満たす数列は $ (1,1,2,2),(1,2,1,2),(1,2,2,1),(2,1,1,2),(2,1,2,1),(2,2,1,1) $ の $ 6 $ 個です。 ### Constraints - $ 1\leq T\leq 10^5 $ - $ 2\leq M\leq 10^9 $ - $ 1\leq N $ - $ 1\leq C_i $ - $ \sum_{i=1}^N C_i\leq 5000 $ - 全てのテストケースに対する $ N $ の総和は $ 3\times 10^5 $ 以下 - 入力はすべて整数