杭电多校第三场 HDU - 6608

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 1e7+10;
ll p;
int a[maxx+10];
bool pri[maxx+10];
int cnt1 = 0;
bool is_prime(ll x)
{
  for(int i=0;i<cnt1&&(ll)a[i]*a[i] <= x;i++){
      if(x % a[i] == 0)
          return 0;
  }
  return 1;
}
void prime()
{
  for(int i=2;i<=maxx;i++)
  {
      if(!pri[i])
          a[cnt1++] = i;
      for(int j=0;(j<cnt1 && (ll)i*a[j]<=maxx);j++)
      {
          pri[i*a[j]] = 1;
          if(i%a[j] == 0)
              break;
      }
  }
}
ll multi_mod(ll a,ll b)
{
  ll cnt = 0;
  while(b)
  {
      if(b & 1){
          cnt = (cnt + a)%p;
      }
      a = (a*2)%p;
      b>>=1;
  }
  return cnt%p;
}
//分数幂，则a/b mod c==(a * b^(c-2))mod c;
ll pow_mod(ll a,ll b){
  ll cnt=1;
  while(b){
      if(b&1)
          cnt=multi_mod(cnt,a);
      a=multi_mod(a,a);
      b>>=1;
  }
  return cnt%p;
}
int main()
{
  int t;
  prime();
  ll k;
  scanf("%d",&t);
  while(t--)
  {
      scanf("%lld",&p);
      k = p-2;
      while(!is_prime(k)){
          k-=2;
      }
      ll ans = 1;
      for(ll i = k+1;i<p-1;i++)
      {
          ans = multi_mod(ans,pow_mod(i,p-2));
      }
      printf("%lld\n",ans);
  }
  return 0;
}