题意：
给你一个1e9-1e14的质数P，让你找出这个质数的前一个质数Q，然后计算Q！mod P
题解：
1e14的数据范围pass掉一切素数筛法，考虑Miller-Rabin算法。
米勒拉宾算法是一种判断素数的随机化算法，由于其随机性，它不能保证总是正确的，但其对于一个素数，总会返回素数的结果，对于一个合数，才有极小概率返回素数的结果（假阳性）。
米勒拉宾算法对于单个素数的判断时间复杂度为$O(log^3n)$.（因为1e14相乘会爆longlong，模乘要写成龟速乘，因此要多一个log）
1849年，高斯猜想，素数分布密度符合如下的公式，$\pi(x) \approx x/lnx$，其中$\pi(x)$为不超过x的素数个数，根据这个公式，1e14以内，两个素数间隔平均只有46个左右，相当稠密了。
因此，只需要用米勒拉宾算法从P-1一个一个判断，直到找到另一个素数Q。
再给出一个结论，对于任意素数n，(n-2)! mod n = 1，因为从2到n-2，互为模n逆元的数捉对出现，证明可参考离散数学课本数论部分。
因此，计算Q！ mod P只需计算 $\prod^{P-2}_{i=Q+1}i$ 再利用费马小定理快速幂求逆元即可。
需要注意，1e14相乘会爆longlong，可以用_int128，但稳妥一点的方法是用思想类似于快速幂的龟速乘。
#include<bits/stdc++.h>
#define Times 10
#define LL long long
#define ll long long
using namespace std; ll multi(ll a, ll b, ll m) {
ll ans = ; a %= m;
while (b) {
if (b & )ans = (ans + a) % m;
a = (a + a) % m; b >>= ;
} return ans;
} ll quick_mod(ll a, ll b, ll m) {
ll ans = ; a %= m;
while (b) {
if (b & )ans = multi(ans, a, m);
a = multi(a, a, m); b >>= ;
} return ans;
} bool Miller_Rabin(ll n) {
if (n == )return true;
if ((n < ) || !(n & ))return false;
ll m = n - ;
ll k = ;
while ((m & ) == ) {
k++; m >>= ;
}
for (ll i = ; i < Times; i++) {
ll a = rand() % (n - ) + ;
ll x = quick_mod(a, m, n);
ll y = ;
for (ll j = ; j < k; j++) {
y = multi(x, x, n);
if (y == && x != && x != n - )return false;
x = y;
} if (y != )return false;
} return true;
} long long quick_mul(long long x,long long y,long long mod)
{
long long ans=;
while(y!=){
if(y&==)ans+=x,ans%=mod;
x=x+x,x%=mod;
y>>=;
}
return ans;
}
long long quick_pow(long long x,long long y,long long mod)
{
long long sum=;
while(y!=){
if(y&==)sum=quick_mul(sum,x,mod),sum%=mod;
x=quick_mul(x,x,mod),x%=mod;
y=y>>;
}
return sum;
} int main(){
// LL pp=1;
// for(int i=1;i<=999999937;i++){
// pp=pp*i%1000000007;
// }
// printf("%lld\n",pp);
int t;
scanf("%d",&t);
while(t--){
LL q;
scanf("%lld",&q);
LL p;
for(register LL i=q-;;i-=){
if(Miller_Rabin(i)){
p=i;break;
}
}
// printf("%d\n",p);
LL ans=; for(LL j=p+;j<=q-;j++){
ans=quick_mul(ans,j,q);
}
printf("%lld\n",quick_pow(ans,q-,q));
}
return ;
}