# [ccNOV14] Fombinatorial

## 描述 Description

You are given a function f which is defined as :

$f(N)=1^1*2^2*3^2*...*(N-1)^{N-1}*N^N$

Your task is to find the value of $\frac{f(N)}{f(r)*f(N-r)}$. As it will be a large number output it modulo $M$.

## 输入格式 InputFormat

First line contains T , number of test cases to follow.

Next follows T test case.

First line of ever test case contain 3 space separated integers N , M and Q.

Next Q line follows , each line contain r.

## 输出格式 OutputFormat

For every test case , output Q lines , each line containing the answer.

1
5 24 2
2
3

## 样例输出 SampleOutput

8
8

CodeChef POWERMUL

$a$ 在模 $m$ 意义下的乘法逆元为 $a^{\phi(m)-1} \ mod \ m$

$x_i,y_i,z_i$ 表示分别使 $p_{i}^{x_i},p_{i}^{y_i},p_{i}^{z_i}$$f[n],f[r],f[n-r]$ 的因数时最大的指数。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define ll long long
const ll inf=0x7fffffff/27.11;
const ll maxn=200005;
ll i,j,t,n,m,l,r,k,z,y,x;
vector <ll> prime,fac;
vector <ll>::iterator vi;
ll f[maxn];
bool isp[maxn];
ll T,phi,ans,q;
inline void getprime()
{
ll i,j,t;
memset(isp,true,sizeof(isp));
prime.clear();
for (i=2;i<=maxn;i++) if (isp[i])
{
for (j=2*i;j<=maxn;j+=i) isp[j]=false;
prime.push_back(i);
}
}
inline void getfac(ll n)
{
ll i,j,t=sqrt(n+0.5);
phi=n;
fac.clear();
for (vi=prime.begin();vi!=prime.end() && *vi<=t;vi++) if (n%(*vi)==0)
{
phi=phi/(*vi)*(*vi-1);
fac.push_back(*vi);
while (n%(*vi)==0) n/=*vi;
}
if (n>1)
{
phi=phi/n*(n-1);
fac.push_back(n);
}
}
inline ll qpow(ll a,ll b,ll m)
{
ll i,j,t=1;
while (b)
{
if (b&1) t=t*a%m;
a=a*a%m;
b>>=1;
}
return t;
}
inline ll index(ll a,ll n)
{
ll i,j,t,ans=0;
i=a;
while (i<=n)
{
t=(ll)n/i;
ans+=t*(t+1)/2*i;
i*=a;
}
return ans;
}
int main()
{
getprime();
scanf("%lld",&T);
while (T--)
{
scanf("%lld%lld%lld",&n,&m,&q);
getfac(m);
f[1]=1%m;
for (i=2;i<=n;i++)
{
t=i;
for (vi=fac.begin();vi!=fac.end() && t>=*vi;vi++) while (t%(*vi)==0) t/=*vi;
f[i]=f[i-1]*qpow(t,i,m)%m;
}
while (q--)
{
scanf("%lld",&r);
if (m==1)
{
printf("0\n");
continue;
}
ans=f[n]*qpow(f[n-r],phi-1,m)%m*qpow(f[r],phi-1,m)%m;
for (vi=fac.begin();vi!=fac.end() && *vi<=n;vi++)
{
t=index(*vi,n)-index(*vi,r)-index(*vi,n-r);
ans=ans*qpow(*vi,t,m)%m;
}
printf("%lld\n",ans);
}
}
return 0;
}