<백준> 11051

이항 계수 2

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

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

출력
(\binom{N}{K})를 10,007로 나눈 나머지를 출력한다.

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, k;
	int d[1001][10001];

	cin >> n >> k;

	for (int i = 0; i <= n; i++)
	{
		d[i][1] = i;
		d[i][0] = 1;
		d[i][i] = 1;
	}

	for (int i = 2; i <= n; i++)
	{
		for (int j = 1; j < i; j++)
		{
			d[i][j] = (d[i - 1][j - 1] + d[i - 1][j]) % 10007;
		}
	}

	cout << d[n][k];
}