Description
大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R取模后的答案即可。R是一个质数。
Input
第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R为模后面T行，每行一对整数N，M，见题目描述 m<=n
Output
共T行，对于每一对N，M，输出1至N！中与M！素质的数的数量对R取模后的值
Sample Input
1 11
4 2
Sample Output
1
数据范围：
对于100%的数据，1 < = N , M < = 10000000
卧槽，这也坑，Wikioi竟然有两个点的R不是质数。。。。。。
还好BZOJ上没有坑，其实打扩展欧几里得比i^(r-2)要快，但是既然他是质数，我当然要好好利用一下了
就是m!*φ(n)/n!，然后预处理m!和φ(n)/n!就行了
1 const 2 maxn=10000000; 3 maxq=10000; 4 var 5 t,r,max,tot:longint; 6 flag:array[0..maxn]of boolean; 7 a,b:array[0..maxn]of int64; 8 n,m:array[0..maxq]of longint; 9 p:array[0..1000000]of longint;10 x,y:int64;11 12 procedure extendedgcd(a,b:longint);13 var14 t:int64;15 begin16 if b=0 then17 begin18 x:=1;19 y:=0;20 exit;21 end;22 extendedgcd(b,a mod b);23 t:=x;24 x:=y;25 y:=t-(a div b)*y;26 end;27 28 procedure pre;29 var30 i,j:longint;31 begin32 for i:=2 to max do33 begin34 if flag[i]=false then35 begin36 inc(tot);37 p[tot]:=i;38 end;39 for j:=1 to tot do40 begin41 if int64(i)*p[j]>max then break;42 flag[i*p[j]]:=true;43 if i mod p[j]=0 then break;44 end;45 end;46 a[0]:=1;47 b[0]:=1;48 flag[1]:=true;49 for i:=1 to max do50 begin51 a[i]:=a[i-1]*i mod r;52 if flag[i] then b[i]:=b[i-1]53 else54 begin55 extendedgcd(i,r);56 if x<0 then x:=x+trunc(x/r)*r+r;57 x:=x mod r;58 b[i]:=(b[i-1]*(i-1)mod r)*x mod r;59 end;60 end;61 end;62 63 procedure main;64 var65 i:longint;66 begin67 read(t,r);68 for i:=1 to t do69 begin70 read(n[i],m[i]);71 if n[i]>max then max:=n[i];72 end;73 pre;74 for i:=1 to t do75 writeln(a[n[i]]*b[m[i]] mod r);76 end;77 78 begin79 main;80 end.