# 魔法【省选模拟赛】

## 求组合数（模数非质数）

Posted by yjjr's blog on March 16, 2018

# code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;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;
}
const int maxn=1e6+6;
int n,x,p,prime[maxn],cnt,Num[maxn],ans;
inline int qpow(int x,int y){
int re=1;
while(y){
if(y&1)re=(ll)re*x%p;
y>>=1,x=(ll)x*x%p;
}
return re;
}
void Pre(int x){
for(int i=2;i*i<=x;i++)
if(!(x%i)){
prime[++cnt]=i;
while(!(x%i))x/=i;
}
if(x>1)prime[++cnt]=x;
}
inline int getgcd(int x,int y){return !x?y:getgcd(y%x,x);}
inline int phi(int x){int re=0;rep(i,1,x-1)if(getgcd(i,x)==1)re++;return re;}
if(!x||x==1)return x;
rep(i,1,cnt){
while(!(x%prime[i])){
x/=prime[i];
Num[prime[i]]+=P;
}
if(x==1)break;
}
return x;
}
int main()
{
//freopen("magic.in","r",stdin);
//freopen("magic.out","w",stdout);
Pre(p);
int Phi=phi(p),C=1,record=1;
rep(i,1,n){