Description

Original source: BZOJ 2142

The annual Christmas season is approaching. Every year, Little E receives many gifts and, of course, gives many gifts in return. Different people hold varying levels of importance in Little E's heart, and those who carry more weight receive more gifts.

Little E has purchased $n$ gifts from the store, intending to distribute them among $m$ people, with $w_i$ gifts designated for the $i$-th person. Please help calculate the number of possible gifting schemes (two schemes are considered different if and only if there exists at least one person who receives different gifts in the two schemes). Since the number of schemes can be very large, you only need to output the result modulo $P$.

Input Format

The first line of input contains a positive integer $P$, representing the modulus;

The second line contains two positive integers $n$ and $m$, representing the number of gifts Little E has bought and the number of gift recipients, respectively;

The following $m$ lines each contain a single positive integer $w_i$, representing the number of gifts Little E intends to give to the $i$-th person.

Output Format

If no feasible scheme exists, output Impossible. Otherwise, output an integer representing the number of schemes modulo $P$.

Sample 1

Details of the $12$ schemes are as follows: $\{1\}\{2,3\},\{1\}\{2,4\},\{1\}\{3,4\},\{2\}\{1,3\},\{2\}\{1,4\},\{2\}\{3,4\},\{3\}\{1,2\},\{3\}\{1,4\},\{3\}\{2,4\},\{4\}\{1,2\},\{4\}\{1,3\},\{4\}\{2,3\}$.

100
4 2
1
2

12

Constraints & Hints

Let $P=p_1^{c_1} \times p_2^{c_2} \times p_3^{c_3} \times \cdots \times p_t ^{ c_t}$, where $p_i$ are prime numbers.

For $100\%$ of the data, $1\le n\le 10^9,1\le m\le 5,1\le p_i^{c_i}\le 10^5$.