package yukicoder; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main{ public static void main(String[] args)throws Exception{ new Main().solve(); } ArrayList primes=new Prime().primeList((int)Math.sqrt(1000000000)); void solve(){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); Prime p=new Prime(); for(int i=0;i=m){ return 0; }else if(n<=2*Math.pow(10,5)){ int ans=1; for(int i=1;i<=n;i++){ ans=ans*i%m; } return ans; }else if(new Prime().primeFactorF(primes, m).size()>=2)return 0; else{ int ans=m-1; for(int i=m-1;i>=n+1;i--){ int a=ans*inverse_element(i, m); while(a<0)a+=m; ans=ans*inverse_element(i, m); } return ans; } } class Prime{ boolean[] isPrimeArray(int max){ boolean[] isPrime=new boolean[max+1]; Arrays.fill(isPrime, true); isPrime[0]=isPrime[1]=false; for(int i=2;i*i<=max;i++){ if(isPrime[i]){ for(int j=2;j*i<=max;j++){ isPrime[j*i]=false; } } } return isPrime; } ArrayList primeList(int max){ boolean[] isPrime=isPrimeArray(max); ArrayList primeList=new ArrayList(); for(int i=2;i<=max;i++){ if(isPrime[i]){ primeList.add(i); } } return primeList; } ArrayList primeFactorF(ArrayList primeList,long num){ ArrayList ret=new ArrayList(); for(int p:primeList){ int exp=0; while(num%p==0){ num/=p; exp++; } if(exp>0)ret.add(new Factor(p,exp)); } if(num>1)ret.add(new Factor((int)num,1)); return ret; } } class Factor{ int base,exp; Factor(int base,int exp){ this.base=base; this.exp=exp; } } /** * ax=1 mod p * となる逆元x=a^(-1)を求める。 * pが素数でないときは逆元は存在しない(正しくない値を返す)。 * 拡張ユークリッドの控除法を用いた。 */ int inverse_element(int a,int p){ return extended_Euclid(a, 0, 1, 0, p, 1)[0]; } /** *ax=1 mod p となるxを求める。 *ax+py=1を満たす、(x,y)を求めればよい。 *拡張ユークリッドの控除法を用いる。 *参考 *http://arc360.info/algo/privatekey.html */ /** * extende_Euclid(1,0,a,0,1,b) * が最初に代入する値。 * ax+by=gcd(a,b)を満たす、(x,y)とgcd(a,b)を * {x,y,gcd(a,b)}の形で返す。 * ただし、a>bとする。 */ int[] extended_Euclid(int x0,int y0,int c0,int x1,int y1,int c1){ System.out.println(x0+" "+y0+" "+c0+" "+x1+" "+y1+" "+c1); if(c0