5607. 조합 (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Solution{

	static int T;
	static long dp[];
	static int n, r;
	static final int P = 1234567891;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		dp = new long[1000001]; // dp[i] = i! % P
		dp[1] = 1;

		for (int i = 2; i <= 1000000; i++) {
			dp[i] = (dp[i - 1] * i) % P;
		}

		for (int t = 1; t <= T; t++) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			r = Integer.parseInt(st.nextToken());
			

			// 분모
			long bottom = (dp[n-r] * dp[r]) % P;
			
			long B = pow(bottom, P-2);
			long ans = (dp[n] * B) % P;
			
			sb.append("#").append(t).append(" ").append(ans).append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		
	}

	static long pow(long a, int b) {
		if (b == 0)
			return 1;
		else if (b == 1)
			return a;
		if (b % 2 == 0) { //
			long tmp = pow(a, b / 2);
			return (tmp * tmp) % P;
		}
		long tmp = pow(a, b - 1);
		return (tmp * a) % P;
	}
}