P2183 [CTT] Gift

Christmas is coming. Every year, Xiao E receives many gifts, and of course he also gives many gifts. Different people have different levels of importance in Xiao E’s mind; the more important someone is, the more gifts they receive.

Xiao E bought $n$ gifts from a store and plans to give them to $m$ people, where the number of gifts given to the $i$-th person is $w_i$. Please help compute the number of ways to give out the gifts (two ways are considered different if and only if there exists a person who receives different gifts in the two ways). Since the number of ways can be very large, you only need to output the result modulo $P$.

The first line contains an integer $P$, the modulus. The second line contains two integers $n$ and $m$, representing the number of gifts Xiao E bought and the number of recipients, respectively. Lines $3$ to $(m + 2)$: each line contains an integer; the integer on the $(i + 2)$-th line $w_i$ denotes the number of gifts given to the $i$-th person.

If there is no feasible way, output `Impossible`; otherwise, output a single integer representing the number of ways modulo $P$.

### Explanation for Sample 1 Separated by `/`, where the parts before and after `/` represent the gift IDs for the first and second persons, respectively. The $12$ possible ways are as follows: ```plain 1/23 1/24 1/34 2/13 2/14 2/34 3/12 3/14 3/24 4/12 4/13 4/23 ``` ### Constraints Let $P= \prod_{i=1}^t p_i^{c_i}$, where $p_i$ is a prime. For $15\%$ of the testdata, $n\leq 15$, $m\leq 5$, $p_i^{c_i}\leq 10^5$. In the remaining $85\%$ of the testdata, about $60\%$ satisfy $t\leq 2$, $c_i=1$, $p_i\leq 10^5$, and about $30\%$ satisfy $p_i\leq 200$. For $100\%$ of the testdata, $1\leq n\leq 10^9$, $1\leq m\leq 5$, $1\leq p_i^{c_i}\leq 10^5$, $1\leq w_i \leq P\leq 10^9$. Translated by ChatGPT 5