首先我们看到题目要求的是1~N！内有M！互质的个数
N!>M！，而我们是知道在M！以内与M！互质的数的个数，即phi(M!)
但是M!~N！内与M！互质的数有多少个呢？
对于每个互质的数，如果我们给他都加上M！，那一定也和M！互质
所以1~N!之间与M！互质的数为phi(M!)*(N!/M!)
由于M！很大，不能有以前的方法计算，我们可以考虑用公式计算
phi(m)=m*(p1-1)/p1*(p2-1)/p2……*(pk-1)/pk pk为m的素因数
因为m！所包含的素因数只可能在1~m内，这是比较容易计算出来的
简化可得ans=N!*(p1-1)/p1*(p2-1)/p2……*(pk-1)/pk
由于这道题又牵扯到了除法取模，所以又要用到扩展欧几里得
然后这道题是坑爹的多测，我们要预处理素数表，阶乘表等等，具体见程序
var a,b,d:array[..] of int64;
x,y:array[..] of longint;
v:array[..] of boolean;
prime:array[..] of longint;
tot,j,i,t,p,n,m:longint;
r,k,ans,s:int64; procedure exgcd(a,b:int64);
var z:int64;
begin
if b= then
begin
r:=;
k:=;
end
else begin
exgcd(b,a mod b);
z:=r;
r:=k;
k:=z-(a div b)*k;
end;
end; begin
readln(t,p);
for i:= to t do
begin
readln(x[i],y[i]);
if x[i]>m then m:=x[i];
end;
for i:= to m do //筛素数
begin
if not v[i] then
begin
inc(tot);
prime[tot]:=i;
end;
for j:= to tot do
begin
if i*prime[j]>m then break;
v[i*prime[j]]:=true;
if i mod prime[j]= then break;
end;
end;
d[]:=;
a[]:=;
b[]:=;
for i:= to m do
begin
a[i]:=a[i-];
b[i]:=b[i-];
if not v[i] then
begin
a[i]:=a[i]*int64(i-) mod p;
b[i]:=b[i]*int64(i) mod p;
end;
d[i]:=d[i-]*int64(i) mod p;
end;
for j:= to t do
begin
ans:=d[x[j]]*a[y[j]] mod p;
exgcd(b[y[j]],p);
r:=(r+p) mod p;
writeln(ans*r mod p);
end;
end.