/*
(C n,m) % p
*/
#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
ll n, m, p;
ll pow_m(ll a, ll k, ll p) {
ll ans = 1;
ll tmp = a % p;
while (k) {
if (k & 1)ans = ans * tmp % p;
tmp = tmp * tmp % p;
k >>= 1;
}
return ans;
}
ll C(ll n, ll m, ll p) {
if (m > n)return 0;
ll a = 1, b = 1;
for (int i = 1; i <= m; i++) {
a = a * (n + i - m) % p;
b = b * i % p;
}
return a * pow_m(b, p - 2, p) % p;
}
ll Lucas(ll n, ll m, ll p) {
ll ans = 1;
while (n && m) {
ans = ans * C(n % p, m % p, p) % p;
n /= p;
m /= p;
}
return ans;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%lld%lld%lld", &n, &m, &p);
printf("%lld\n", Lucas(n, m, p));
}
return 0;
}
/*
Euler screen
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
int n, cnt = 0;
int prime[100001];// Story of Vegetarian
bool vis[100001]; // Guaranteed not to make a number of prime numbers
scanf("%d", &n);
memset(vis, false, sizeof(vis));// initialization
memset(prime, 0, sizeof(prime));
for (int i = 2; i <= n; i++) {
if (!vis[i])// Not the number of prime numbers currently found
prime[cnt++] = i;// Find prime numbers
for (int j = 0; j < cnt && i * prime[j] <= n; j++) {
vis[i * prime[j]] = true;// The number of prime numbers found does not access
if (i % prime[j] == 0) break;// Key! Intersection Intersection Intersection
}
}
printf("%d\n", cnt);
return 0;
}
/*
Quick -order multiplication
*/
#include <bits/stdc++.h>
#define _xx ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
typedef long long LL;
//n![1~10]：1,2,6,24,120,720,5040,40320,362880,3628800,
const int mod = 1000000007;
int prime[2000];
bool vis[10005];
int cnt = 0;
void init() {
int m = (int) sqrt(10005) + 1;
for (int i = 2; i <= m; i++) {
if (!vis[i]) {
for (int j = i * 2; j <= 10005; j += i) {
vis[j] = true;
}
}
}
for (int i = 2; i <= 10000; i++) if (!vis[i])prime[cnt++] = i;
}
LL poww(LL a, LL b, LL m) {
LL ans = 1;
while (b) {
if (b & 1) ans = ans * a % m;
a = a * a % m;
b >>= 1;
}
return ans;
}
int main() {
_xx;
init();
int n;
while (cin >> n) {
LL ans = 1;
for (int i = 0; i < cnt && prime[i] <= n; i++) {
int k = 0;
int t = n;
while (t) {
k += t / prime[i];
t /= prime[i];
}
ans = ans * poww(prime[i], k, mod) % mod;
}
cout << ans << endl;
}
}
/*
Euler function (Euler screen)
*/
const int N = 10000010;
int phi[N], prime[N];
int tot; // A total of prime numbers
/*
1. pHI (p) = P-1 is only p and p and p with only p and p, which is only p and p, because the factor P and p are only P and P.
2. If I mod p = 0, then pHI (i * p) = pHI (i) * p
3. If I MOD P 3 0, then pHI (i * p) = pHI (i) * (p-)
*/
void Euler() {
memset(phi, 0, sizeof(phi));
phi[1] = 1;
for (int i = 2; i < N; i++) {
if (!phi[i]) {
phi[i] = i - 1;
prime[tot++] = i;
}
for (int j = 0; j < tot && 1ll * i * prime[j] < N; j++) {
if (i % prime[j])
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
else {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
}
Follow -up follow -up update