[[TableOfContents]]

= 오늘의 문제 =
 * [https://www.codeground.org/practice/practiceProbView.do?probId=5|이항계수의 합]
= 참가자 =
 * 황창재
 * 15이원준
= 코드 =
== 황창재 ==
{{{
// 아래 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
#include <stdio.h>

typedef unsigned long long ULL;
#define T 1000000007

#pragma warning(disable:4996)

ULL fctrl[2000003];

void clearFctrl() {
	int i;
	for (i = 0; i < 2000003; i++) {
		if (i) {
			fctrl[i] = (fctrl[i - 1] * i) % T;
		}
		else fctrl[i] = 1;
	}
}

ULL getC(ULL n, ULL k) {
	ULL i;
	ULL product;
	ULL A, B;
	ULL p;

	A = fctrl[n];
	B = (fctrl[k] * fctrl[n - k] )%T;

	p = T-2;
	while (p != 1) {
		if (p % 2) {
			A = (A*B) % T;
		}
		B = (B*B) % T;
		p = p / 2;
	}
	product = (A*B) % T;

	return product;
}

int main(void) {
	/* 아래 freopen 함수는 input.txt를 read only 형식으로 열고, 표준입력(키보드) 대신 input.txt 로 부터 읽어오겠다는 의미의 코드입니다.
	만약 본인 PC 에서 테스트 할 때는, 입력값을 input.txt에 저장한 후 freopen 함수를 사용하면
	그 아래에서 scanf 함수를 사용하여 표준입력 대신 input.txt 파일로 부터 입력값을 읽어 올 수 있습니다.
	또한, 본인 PC에서 freopen 함수를 사용하지 않고 표준입력을 사용하여 테스트하셔도 무방합니다.
	단, Codeground 시스템에서 "제출하기" 할 때에는 반드시 freopen 함수를 지우거나 주석(//) 처리 하셔야만 합니다. */
	// freopen("input.txt", "r", stdin);

	setbuf(stdout, NULL);

	int TC;
	int test_case;

	ULL sum;

	ULL N, M;

	clearFctrl();

	scanf("%d", &TC);
	for (test_case = 1; test_case <= TC; test_case++) {
		// 이 부분에서 알고리즘 프로그램을 작성하십시오. 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
		scanf("%d %d", &N, &M);

		sum = getC(N + M + 2, M + 1) - 1;

		// 이 부분에서 정답을 출력하십시오.
		printf("Case #%d\n", test_case);
		printf("%llu\n", sum);
	}

	return 0;	// 정상종료 시 반드시 0을 리턴해야 합니다.
}
}}}

= 아이디어 =
== 황창재 ==
 * nCr + nCr+1 == n+1Cr+1 을 이용하여 식을 간략화함
 * nCr == n! / r!(n-r)! 을 이용해야 하는데 큰수의 나눗셈에서 오차가 발생함. 
   * 결과적으로 A!/B! 을 1,000,000,007로 나눈 나머지를 구해야함. 페르마의 소정리 ( A! == n! , B! == r!(n-r)! )
     x^(p-1) mod p == 1 mod p 를 이용하여
     A x B^(p-2) mod p == A x B mod p 로 나타내어 계산식에 나눗셈을 제거함. 
 * 반복 제곱법 알고리즘을 통해 A x B^(p-2)를 빠르게 계산함.
 * 팩토리얼값은 매번 쓰일일이 많으며 시간도 많이 걸리기 때문에 필요한 범위까지 미리 계산하여 사용.

== 15이원준 ==
 * 수알못이라 포기합니다...ㅠ