~~看上去我的式子和别人的不一样所以我就来水一波233~~
我是这样考虑的：
对于这几个礼物，我们可以枚举排列，然后前$w_1$个给第一个人，之后的$w_2$个给第二个人……但是这样会有重复的，即有可能某个人拿的礼物的顺序不一样但是本质是相同的，这样的话，就要再除以$w_i!$，不要忘了剩下没分的那部分也有重的，所以最后的式子就是$\dfrac{n!}{(n-tot)!w_1!w_2!w_3!w_4!w_5!}$。
这样运用扩展lucas的思想就可以算了。
```C++
#include <cstdio>
#include <cmath>
typedef long long LL;
LL n, m, P;
LL w[6], tot;
void exgcd(LL a, LL b, LL &x, LL &y, LL &d) {
if (!b) {
d = a;
x = 1;
y = 0;
} else {
exgcd(b, a%b, y, x, d);
y -= a / b * x;
}
}
LL pow_mod(LL x, LL p, LL mod) {
LL ans = 1;
for (; p; p>>=1, x=x*x%mod) if (p&1) ans = ans * x % mod;
return ans;
}
LL fac(LL n, LL p, LL pk) {
if (!n) return 1;
LL ans = 1;
for (int i = 2; i <= pk; ++i) if (i%p) ans = ans * i % pk;
ans = pow_mod(ans, n/pk, pk);
for (int i = 2; i <= n%pk; ++i) if (i%p) ans = ans * i % pk;
return ans * fac(n/p, p, pk) % pk;
}
LL inv(LL n, LL mod) {
LL x, y, d;
exgcd(n, mod, x, y, d);
return (x%=mod) < 0 ? x+mod : x;
}
LL CRT(LL b, LL mod) {
return b*(P/mod)%P*inv(P/mod, mod)%P;
}
LL calc(LL x, LL p) {
LL k = 0;
for (; x; x /= p) k += x / p;
return k;
}
LL C(LL p, LL pk) {
LL u = fac(n, p, pk), d = inv(fac(n-tot, p, pk), pk);
for (int i = 1; i <= m; ++i) {
d = d * inv(fac(w[i], p, pk), pk) % pk;
}
LL k = 0;
k += calc(n, p);
k -= calc(n-tot, p);
for (int i = 1; i <= m; ++i) {
k -= calc(w[i], p);
}
return u * d % pk * pow_mod(p, k, pk) % pk;
}
void work() {
if (tot > n) {
puts("Impossible");
return;
}
LL ans = 0, tmp = P, pk;
LL lim = sqrt(P) + 5;
for (int i = 2; i <= lim; ++i) if (tmp % i == 0) {
pk = 1;
while (tmp % i == 0) pk*=i, tmp/=i;
ans = (ans + CRT(C(i, pk), pk)) % P;
}
if (tmp > 1) {
ans = (ans + CRT(C(tmp, tmp), tmp)) % P;
}
printf("%lld\n", ans);
}
int main() {
scanf("%lld%lld%lld", &P, &n, &m);
for (int i = 1; i <= m; ++i) scanf("%lld", &w[i]), tot += w[i];
work();
return 0;
}
```