2142: 礼物

Time Limit: 10 Sec  Memory Limit: 259 MB

Submit: 1313  Solved: 541

[][][]

Description

一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。小E从商店中购买了n件礼物，打算送给m个人，其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模P后的结果。

Input

输入的第一行包含一个正整数P，表示模；第二行包含两个整整数n和m，分别表示小E从商店购买的礼物数和接受礼物的人数；以下m行每行仅包含一个正整数wi，表示小E要送给第i个人的礼物数量。

Output

若不存在可行方案，则输出“Impossible”，否则输出一个整数，表示模P后的方案数。

Sample Input

100 4 2 1 2

Sample Output

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。

HINT

Source

Solution

扔下模板走人。

Code

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define LL long long#define MAXN 100010inline int read(){	int x=0,f=1; char ch=getchar();	while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}	while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}	return x*f;}#define Pa pair
          
           #define MP make_pair#define X first#define C secondint N,M,P,w[MAXN];inline LL Pow(LL x,LL y) {LL re=1; for (LL i=y; i; i>>=1,x=x*x) if (i&1) re=re*x; return re;}inline LL Pow(LL x,LL y,LL p) {LL re=1; for (LL i=y; i; i>>=1,x=x*x%p) if (i&1) re=re*x%p; return re;}inline void Exgcd(LL a,LL b,LL &x,LL &y) {if (!b) {x=1,y=0; return;} else Exgcd(b,a%b,y,x),y-=a/b*x;}inline LL Inv(LL x,LL p) {LL a,b; Exgcd(x,p,a,b); return (a%p+p)%p;}inline Pa Fac(LL x,LL p,LL c,LL pc){ if (x==1 || !x) return MP(1,0); int las=x%pc; LL re2=1,re1; for (int i=1; i<=las; i++) { if (!(i%p)) continue; re2=re2*i%pc; } if (x>=pc) { re1=re2; for (int i=las+1; i
           
            1) p[++cnt]=x,pex[cnt]=x,ex[cnt]=1;}LL an[MAXN];inline LL CRT(int n,int m){ LL re=0; for (int i=1; i<=cnt; i++) an[i]=Lucas(n,m,p[i],ex[i],pex[i]); for (int i=1; i<=cnt; i++) (re+=P/pex[i]*Inv((P/pex[i])%pex[i],pex[i])%P*an[i]%P)%=P; return re;}int main(){ P=read(); Divide(P); N=read(),M=read(); LL tot=0; for (int i=1; i<=M; i++) w[i]=read(),tot+=w[i]; if (tot>N) return puts("Impossible"),0; LL ans=CRT(N,tot); for (int i=1; i<=M; i++) { ans=ans*CRT(tot,w[i])%P; tot-=w[i]; } printf("%lld\n",ans); return 0;}