卢卡斯定理

$C_a^b=C_{a\%p}^{b\%p} ~C_{a/p}^{b/p}~(mod~~p)$

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while(n-->0) {
            long a = scanner.nextLong();
            long b = scanner.nextLong();
            int p = scanner.nextInt();
            System.out.println(lucas(a,b,p));
        }
    }

    private static long lucas(long a, long b, int p) {
        if(a<p&&b<p) return C(a,b,p);
        return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
    }

    private static long C(long a, long b,int p) {
        if(b>a) return 0;
        long res = 1,i,j;
        for(i = 1,j = a; i <= b; i ++, j--) {
            res = res*j%p;
            res = res*qmi(i,p-2,p)%p;
        }
        return res;
    }

    private static long qmi(long a, int k, int m) {
        long res = 1;
        while(k!=0) {
            if((k&1)==1)res = res * a % m;
            a = a*a %m;
            k>>=1;
        }
        return res;
    }
}