두 정수 \(n\)과 \(r\)이 주어질 때, 다음과 같이 정의되는 조합의 값을 구하여라.

\(\displaystyle \binom nr=\frac{n!}{r!(n-r)!}\)

단, 값이 매우 클 수 있으므로 \(\binom nr\)을 \(1,000,000,007\)로 나눈 나머지를 출력한다.

이 문제에서 \(n\)과 \(r\)은 최대 \(1,000,000\)이다. 따라서 파스칼의 삼각형을 직접 만드는 방법으로는 문제를 해결할 수 없다.

또한 나머지를 계산하는 과정에서는 일반적인 나눗셈을 그대로 사용할 수 없다. 대신 모듈로 역원을 이용해야 한다.

정수 \(a\)에 대하여 다음 식을 만족하는 정수 \(x\)를 \(a\)의 모듈로 역원이라고 한다.

\(ax\equiv1\pmod {1,000,000,007}\)

\(1,000,000,007\)은 소수이다. 페르마의 소정리를 이용하면 \(a\)의 모듈로 역원을 다음과 같이 구할 수 있다.

\(a^{1,000,000,005}\bmod 1,000,000,007\)

따라서 다음 식을 이용하여 답을 계산할 수 있다.

\(\displaystyle\binom nr\equiv n!\times\left(r!(n-r)!\right)^{1,000,000,005}\pmod {1,000,000,007}\)

단순히 거듭제곱의 지수만큼 곱셈을 반복하면 제한 시간 안에 답을 구할 수 없다. 큰 지수의 거듭제곱을 효율적으로 계산해야 한다.

입력

첫째 줄에 두 정수 \(n\)과 \(r\)이 공백으로 구분되어 주어진다.

• \(1\le n\le1,000,000\)
• \(0\le r\le n\)

출력

\(\binom nr\)을 \(1,000,000,007\)로 나눈 나머지를 출력한다.

예제 입력 1

5 2

예제 출력 1

10

예제 설명 1

먼저 팩토리얼과 분모를 \(1,000,000,007\)로 나눈 나머지를 계산한다.

• \(5!\bmod1,000,000,007=120\)
• \(2!\times3!\bmod1,000,000,007=12\)

\(12\)의 모듈로 역원은 다음과 같다.

\(12^{1,000,000,005}\bmod1,000,000,007=83,333,334\)

따라서 답은 다음과 같다.

\(120\times83,333,334\bmod1,000,000,007=10\)

예제 입력 2

1000000 500000

예제 출력 2

996692777

예제 설명 2

먼저 필요한 팩토리얼을 \(1,000,000,007\)로 나눈 나머지를 계산한다.

• \(1,000,000!\bmod1,000,000,007=641,102,369\)
• \(500,000!\bmod1,000,000,007=154,425,679\)

분모를 \(1,000,000,007\)로 나눈 나머지는 다음과 같다.

\(154,425,679^2\bmod1,000,000,007=167,680,011\)

\(167,680,011\)의 모듈로 역원은 다음과 같다.

\(167,680,011^{1,000,000,005}\bmod1,000,000,007=643,827,145\)

따라서 답은 다음과 같다.

\(641,102,369\times643,827,145\bmod1,000,000,007=996,692,777\)