记录编号	449345	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]礼物(魏铭)	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2017-09-14 07:52:39	内存使用	7.92 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int power(int x,int y,int p){
    int ans=1;
    for (;y;y>>=1,x=1ll*x*x%p)
        if (y&1) ans=1ll*ans*x%p;
    return ans;
}
int getpow(int x,int p){
    return x>=p?getpow(x/p,p)+x/p:0;
}
int n,m,p,cnt,prime[20],pow[20];
void factor(int p){
    for (int i=2;i*i<=p;i++)
    if (p%i==0){
        prime[++cnt]=i;
        while (p%i==0) pow[cnt]++,p/=i;
    }
    if (p>1) prime[++cnt]=p,pow[cnt]=1;
}
const int N=1e5+10;
struct _mod{
    int jc[N],p,mod;
    void init(int P,int Mod){
        p=P;mod=Mod;
        jc[0]=1;
        for (int i=1;i<mod;i++) jc[i]=1ll*jc[i-1]*(i%p?i:1)%mod;
    }
    int calc(int n){//求n!%mod
		return n>=p?1ll*jc[n%mod]*power(jc[mod-1],n/mod,mod)%mod*calc(n/p)%mod:jc[n];
    }
}base[20];
int mi[20],res[20],mod[20],phi[20];
void del(int x){
    for (int i=1;i<=cnt;i++){
        int r=base[i].calc(x);
        mi[i]-=getpow(x,prime[i]);
        res[i]=1ll*res[i]*power(r,phi[i]-1,mod[i])%mod[i];
    }
}
int main()
{
    freopen("nt2011_gift.in","r",stdin);
    freopen("nt2011_gift.out","w",stdout);
    scanf("%d%d%d",&p,&n,&m);
    factor(p);
    for (int i=1;i<=cnt;i++){
        mod[i]=1;
        for (int j=0;j<pow[i];j++) mod[i]*=prime[i];
        phi[i]=mod[i]/prime[i]*(prime[i]-1);
        base[i].init(prime[i],mod[i]);
        mi[i]=getpow(n,prime[i]);
        res[i]=base[i].calc(n);
    }
	ll sum=0;
    for (int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        sum+=x;del(x);
    }
    if (n<sum) return puts("Impossible"),0;
    del(n-sum);
    ll ans=0;
    for (int i=1;i<=cnt;i++){
        res[i]=1ll*res[i]*power(prime[i],mi[i],mod[i])%mod[i];
        int P=p/mod[i];
        ans=(ans+1ll*res[i]*P*power(P,phi[i]-1,mod[i]))%p;
    }
    printf("%lld\n",ans);
    return 0;
}