题意

有 $1 \sim n$ 的数字，要把这些数字分给 $m$ 个人，第 $i$ 个人要有 $w_i$ 个数字。求分数字的方案数，模 $P$，不保证为质数。无解输出 Impossible。

分析

容易想到组合数计算。如果 $\sum w_i > n$，那么无解。剩下的，先 $n$ 个数字选 $\sum w_i$ 个，然后每个人依次选，第 $i$ 个人可以从剩下的礼物中选择 $w_i$ 个。所以最后的答案如下。

$$C_n^{sum} \times \prod_{i=1}^m C_{\sum_{j=i}^m w_j}^{w_i}$$

这里直接算就好，但是因为要算组合数，且模数不保证是质数，所以要用 $\text{exLucas}$。

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define N 100005
#define int long long
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, m, P, w[N], sum;
int exgcd(int a, int b, int &x, int &y){
    if (b == 0) return x = 1, y = 0, a;
    int k = exgcd(b, a % b, y, x);
    return y -= 1ll * a / b * x, k;
}
il int ksm(int x, int r, int p){
    int ans = 1;
    for (; r; x = 1ll * x * x % P, r >>= 1) if (r & 1) ans = 1ll * ans * x % P; 
    return ans;
}
il int inv(int q, int p){
    int x, y;
    return exgcd(q, p, x, y), x += p, (x >= p ? x - p : x);
}
int fact(int n, int pk, int p){
    if (n == 0) return 1;
    int ans = 1;
    for (int i = 2; i <= pk; i++) if (i % p) ans = 1ll * ans * i % pk;
    ans = ksm(ans, n / pk, pk);
    for (int i = 2; i <= n % pk; i++) if (i % p) ans = 1ll * ans * i % pk;
    return 1ll * ans * fact(n / p, pk, p) % pk;
}
il int CRT(int x, int p){return 1ll * x * inv(P / p, p) % P * (P / p) % P; }
il int C(int n, int m, int pk, int p){
    int s = fact(n, pk, p), x = fact(m, pk, p), y = fact(n - m, pk, p), k = 0;
    for (int i = n; i; i /= p) k += i / p;
    for (int i = m; i; i /= p) k -= i / p;
    for (int i = n - m; i; i /= p) k -= i / p;
    return 1ll * s * inv(x, pk) % pk * inv(y, pk) % pk * ksm(p, k, pk) % pk;
}
il int exLcs(int n, int m, int P){
    int tmp = P, ans = 0;
    for (int i = 2; i * i <= tmp; i++){
        int pk = 1;
        while (tmp % i == 0) pk *= i, tmp /= i;
        ans = (ans + CRT(C(n, m, pk, i), pk)) % P;
    }
    if (tmp > 1) ans = (ans + CRT(C(n, m, tmp, tmp), tmp)) % P;
    return ans;
}
signed main(){
    P = rd(), n = rd(), m = rd();
    for (int i = 1; i <= m; i++) w[i] = rd(), sum += w[i];
    if (n < sum) return puts("Impossible"), 0;
    int res = exLcs(n, sum, P);
    for (int i = 1; i <= m; i++) res = 1ll * res * exLcs(sum, w[i], P) % P, sum -= w[i];
    printf ("%lld\n", res);
    return 0;
}