[Java] 11401. 이항 계수 3

www.acmicpc.net/problem/11401

11401번: 이항 계수 3

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (nCk)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)

출력

 (nCk)를 1,000,000,007로 나눈 나머지를 출력한다.

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_11401 {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st = null;
	static final long P = 1000000007;
	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(in.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		long factorial[] = new long[N+1];
		makeFactorial(factorial);
		
		long bottom = (factorial[N-M] * factorial[M]) % P;
		bottom = power(bottom, P-2);
		System.out.println((factorial[N] * bottom)%P);
		
	}
	
	private static long power(long a, long b) {
		if(b == 0) return 1L;
		else if(b == 1) return a;
		
		if(b%2 == 0) {
			long tmp = power(a, b/2);
			return (tmp * tmp) % P;
		}else {
			long tmp = power(a, b-1);
			return (tmp * a) % P;
		}
	}
	private static void makeFactorial(long[] factorial) {
		factorial[0] = 1;
		for (int i = 1; i < factorial.length; i++) {
			factorial[i] = (factorial[i-1] * i) % P;
		}
	}

}