Gifts

Problem Source

National Team Internal Test 11

Problem Description

Christmas is approaching again. Every year little E receives many gifts and also gives many away. Different people matter differently to little E, and the more important someone is, the more gifts they receive.

Little E bought $n$ gifts from a shop to give to $m$ people, and the $i$-th person is to receive $w_i$ gifts. Please help compute the number of ways to distribute the gifts (two distributions are considered different if and only if at least one person receives a different set of gifts). Since the number of ways may be huge, you only need to output the result modulo $P$.

Input Format

The first line contains a positive integer $P$, the modulus. The second line contains two integers $n$ and $m$, representing the number of gifts little E bought and the number of recipients.

The following $m$ lines each contain a single positive integer $w_i$, the number of gifts for the $i$-th person.

Output Format

If no valid distribution exists, output Impossible; otherwise output one integer: the number of ways modulo $P$.

Sample Input

100
4 2
1
2

Sample Output

12

Constraints

Let $P = p_1^{c_1} \times p_2^{c_2} \times p_3^{c_3} \times \dots \times p_t^{c_t}$, where each $p_i$ is prime.

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