[백준] 11401. 이항계수 구하기

import java.util.Scanner;

public class P11401 {
    static long x, y, gcd, temp;
    public static void main(String[] ar){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        long p = 1000000007;

        long[] factorial = new long[N+1];
        factorial[0] = 1;
        factorial[1] = 1;
        // factorial 구하기
        for(int i=2; i<=N; i++) factorial[i] = (factorial[i-1]*i)%p;
        long denominator = (factorial[K]*factorial[N-K])%p;

        euclidean(p, denominator);
        long result = ((factorial[N]%p)*(y%p))%p;
        if(result<0) result += p;
        System.out.println(result);
    }

    public static void euclidean(long B, long p){
        if(B%p>0){
            euclidean(p, B%p);
            temp = y;
            y = x - (B/p)*y;
            x = temp;
        }else{
            x = 0;
            y = 1;
            gcd = p;
        }
    }
}