题目描述
一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E
心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。小E从商店中购买了n件礼物，打算送给m个人
，其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某
个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模P后的结果。
输入
输入的第一行包含一个正整数P，表示模；
第二行包含两个整整数n和m，分别表示小E从商店购买的礼物数和接受礼物的人数；
以下m行每行仅包含一个正整数wi，表示小E要送给第i个人的礼物数量。
输出
若不存在可行方案，则输出“Impossible”，否则输出一个整数，表示模P后的方案数。
样例输入
100
4 2
1
2
4 2
1
2
样例输出
12
【样例说明】
下面是对样例1的说明。
以“/”分割，“/”前后分别表示送给第一个人和第二个人的礼物编号。12种方案详情如下：
1/23 1/24 1/34
2/13 2/14 2/34
3/12 3/14 3/24
4/12 4/13 4/23
【数据规模和约定】
设P=p1^c1 * p2^c2 * p3^c3 * … *pt ^ ct，pi为质数。
对于100%的数据，1≤n≤109，1≤m≤5，1≤pi^ci≤10^5。
【样例说明】
下面是对样例1的说明。
以“/”分割，“/”前后分别表示送给第一个人和第二个人的礼物编号。12种方案详情如下：
1/23 1/24 1/34
2/13 2/14 2/34
3/12 3/14 3/24
4/12 4/13 4/23
【数据规模和约定】
设P=p1^c1 * p2^c2 * p3^c3 * … *pt ^ ct，pi为质数。
对于100%的数据，1≤n≤109，1≤m≤5，1≤pi^ci≤10^5。
如果$\sum w_{i}>n$显然无解，如果$\sum w_{i}<n$可以将最后剩下那些礼物看作给第$m+1$个人。那么答案就是$C_{n}^{w_{1}}*C_{n-w_{1}}^{w_{2}}*...*C_{w_{m+1}}^{w_{m+1}}$，展开之后就是$\frac{n!}{(w_{1})!(w_{2})!...(w_{m+1})!}$，因为模数不一定是质数，所以用扩展卢卡斯求一下即可。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll n,P;
int m;
ll w[10];
ll quick(ll x,ll y,ll mod)
{
ll res=1ll;
while(y)
{
if(y&1)
{
res=res*x%mod;
}
x=x*x%mod;
y>>=1;
}
return res;
}
ll find(ll n,ll p,ll mod)
{
if(!n)
{
return 1ll;
}
ll res=1ll;
for(ll i=2;i<=mod;i++)
{
if(i%p)
{
res*=i,res%=mod;
}
}
res=quick(res,n/mod,mod);
for(ll i=2;i<=n%mod;i++)
{
if(i%p)
{
res*=i,res%=mod;
}
}
return res*find(n/p,p,mod)%mod;
}
ll inv(ll n,ll mod,ll p)
{
ll phi=mod-(mod/p);
return quick(n,phi-1,mod);
}
ll CRT(ll b,ll mod,ll p)
{
return b*inv(P/mod,mod,p)%P*(P/mod)%P;
}
ll C(ll n,int m,ll p,ll mod)
{
ll res=find(n,p,mod);
ll k=0;
for(ll i=n;i;i/=p)
{
k+=i/p;
}
for(int i=1;i<=m;i++)
{
res*=inv(find(w[i],p,mod),mod,p),res%=mod;
for(ll j=w[i];j;j/=p)
{
k-=j/p;
}
}
return res*quick(p,k,mod)%mod;
}
ll ex_lucas(ll n,int m)
{
ll res=0;
ll sum=P;
ll mod;
for(int i=2;1ll*i*i<=P;i++)
{
if(sum%i==0)
{
mod=1ll;
while(sum%i==0)
{
mod*=i;
sum/=i;
}
res+=CRT(C(n,m,i,mod),mod,i),res%=P;
}
}
if(sum!=1)
{
res+=CRT(C(n,m,sum,sum),sum,sum),res%=P;
}
return res;
}
int main()
{
scanf("%lld",&P);
scanf("%lld%d",&n,&m);
ll sum=n;
for(int i=1;i<=m;i++)
{
scanf("%lld",&w[i]);
sum-=w[i];
}
if(sum<0)
{
printf("Impossible");
return 0;
}
w[++m]=sum;
printf("%lld",ex_lucas(n,m));
}