拓展Lucas板子放一手

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;typedef pair
           
             pa;int mod;int plen,p[30],mip[30];void emmmm(){ int k=mod; for(int i=2;i*i<=mod;i++) if(k%i==0) { p[++plen]=i,mip[plen]=1; while(k%i==0)k/=i,mip[plen]*=i; } if(k!=1)p[++plen]=k,mip[plen]=k;}//~~~~~~~~~~~~~~~~~~~分解mod~~~~~~~~~~~~~~~~~~~~~ void exgcd(int a,int b,int &x,int &y){ if(a==0) { x=0,y=1; return ; } else { int tx,ty; exgcd(b%a,a,tx,ty); x=ty-b/a*tx; y=tx; }}LL inv(int A,int B)//不是质数不能用快速幂求逆元!! { int x,y; exgcd(A,B,x,y); return (x%B+B)%B;}//~~~~~~~~~~~~~~~getinv(mod p)~~~~~~~~~~~~~~~~~~~~~~~~LL quick_pow(int A,int p,int mo) { int ret=1; while(p!=0) { if(p%2==1)ret=(LL)ret*A%mo; A=(LL)A*A%mo;p/=2; } return ret;}//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //-----------------------------------------init-----------------------------------------------------------------pa solve(int n,int id)//first p[id]因子个数，second n!除了这些因子的值 { if(n==0)return make_pair(0,1); LL ans=1; int d=n/mip[id]; if(d>0) { for(int i=2;i
            
             n){printf("Impossible\n");return 0;} LL ans=exlucas(n,s); for(int i=1;i<=m;i++) ans=ans*exlucas(s,w[i])%mod, s-=w[i]; printf("%d\n",ans); return 0;}