## 题目

Farmer John keeps a website called ‘FansBlog’ .Everyday , there are many people visited this blog.One day, he find the visits has reached P , which is a prime number.He thinks it is a interesting fact.And he remembers that the visits had reached another prime number.He try to find out the largest prime number Q ( Q < P ) ,and get the answer of Q! Module P.But he is too busy to find out the answer. So he ask you for help. ( Q! is the product of all positive integers less than or equal to n: n! = n * (n-1) * (n-2) * (n-3) *… * 3 * 2 * 1 . For example, 4! = 4 * 3 * 2 * 1 = 24 )

## 输入

First line contains an number T(1<=T<=10) indicating the number of testcases.
Then T line follows, each contains a positive prime number P (1e9≤p≤1e14)

1
1000000007

## 输出

For each testcase, output an integer representing the factorial of Q modulo P.

328400734

## Code

``````#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll MOD;

ll power(ll x, unsigned long long y, ll p) {
ll res = 1LL;
x = x % p;
while (y > 0) {
if (y & 1LL)
res = (res * x) % p;
y = y >> 1LL;
x = (x * x) % p;
}
return res;
}

ll prime = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};

ll qm(ll a, ll b, ll c) {
long long ans = 0, res = a;
while (b) {
if (b & 1)
ans = (ans + res) % c;
res = (res + res) % c;
b >>= 1;
}
return (ll)ans;
}
ll mul(ll a, ll b) { return (ll)(__int128(a) * b % MOD); }
ll qp(ll a, ll b, ll c) {
ll ans = 1, res = a;
while (b) {
if (b & 1)
ans = qm(ans, res, c);
res = qm(res, res, c);
b >>= 1;
}
return ans;
}
__int128 qp2(__int128 a, __int128 b, __int128 c) {
__int128 ans = 1, res = a;
while (b) {
if (b & 1)
ans = qm(ans, res, c);
res = qm(res, res, c);
b >>= 1;
}
return ans;
}
bool Miller_Rabin(ll x) {
ll i, j, k;
ll s = 0, t = x - 1;
if (x == 2)
return true;
if (x < 2 || !(x & 1))
return false;
while (!(t & 1)) {
s++;
t >>= 1;
}
for (i = 0; i < 6 && prime[i] < x; ++i) {
ll a = prime[i];
ll b = qp(a, t, x);
for (j = 1; j <= s; ++j) {
k = qm(b, b, x);
if (k == 1 && b != 1 && b != x - 1)
return false;
b = k;
}
if (b != 1)
return false;
}
return true;
}

__int128 modInverse(__int128 a, __int128 p) { return qp(a, p - 2ll, p); }

ll modFact(ll n, ll p) {
if (p <= n)
return 0;
__int128 res = (p - 1ll);
for (__int128 i = n + 1ll; i < p; i++) {
res = ((res % p) * (modInverse(i, p) % p)) % p;
}
return (ll)res;
}

int main() {
ll t;
scanf("%lld", &t);
while (t-- > 0) {
scanf("%lld", &MOD);
ll i;
for (i = MOD - 1; i > MOD - 2001; i--) {
if (Miller_Rabin(i))
break;
}
printf("%lld\n", modFact(i, MOD));
}
return 0;
}
``````