Description

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$.

Input Format

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.

Output Format

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

100
4 2
1
2

12

100
2 2
1
2

Impossible

Hint

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:

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