AT_abc425_e [ABC425E] Count Sequences 2

You are given a positive integer $ N $ and a sequence of positive integers $ C=(C_1,C_2,\ldots,C_N) $ of length $ N $ . Find, modulo a given positive integer $ M $ , the number of sequences of positive integers that satisfy all of the following conditions. - All elements of the sequence are between $ 1 $ and $ N $ , inclusive. - For each $ i=1,2,\ldots,N $ , the value $ i $ appears exactly $ C_i $ times in the sequence. $ T $ test cases are given, so find the answer for each. $ M $ is common to all $ T $ test cases.

The input is given from Standard Input in the following format: > $ T $ $ M $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ The $ i $ -th test case, $ \mathrm{case}_i $ , is given in the following format: > $ N $ $ C_1 $ $ C_2 $ $ \ldots $ $ C_N $

Output $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 For the first test case, the sequences that satisfy the conditions are $ (1,1,2,2),(1,2,1,2),(1,2,2,1),(2,1,1,2),(2,1,2,1),(2,2,1,1) $ , which is six sequences. ### 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 $ - The sum of $ N $ over all test cases is at most $ 3\times 10^5 $ . - All input values are integers.