[수학 3 단계] 백준 11051번 이항 계수 2 oo

문제

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

입력

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

출력

 (NK)를 10,007로 나눈 나머지를 출력한다.

 

#include <iostream>
#include <vector>
#include<queue>
#include <string>
#include <map>
#include<algorithm>
using namespace std;

long long D[1001][1001];

void init()
{
	D[1][0] = 1;
	D[1][1] = 1;
	for (int i = 2; i <= 1001; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (j == 0 || j == i)
			{
				D[i][j] = 1;
				continue;
			}
			D[i][j] =( D[i - 1][j] % 10007 + D[i - 1][j - 1] % 10007 ) % 10007;
		}
	}
}

int main() {
	init();
	int a, b;
	cin >> a >> b;
	cout << D[a][b] % 10007 << endl;
}