\(Q\)개의 독립적인 질의에 답하시오. 각 질의는 \(\binom{n}{k} \bmod (10^9+7)\), 즉 \(n\)개 중 \(k\)개를 고르는 경우의 수를 묻는다. 팩토리얼과 그 모듈러 역원을 한 번 전처리한 뒤 각 질의를 \(O(1)\)에 답하면 된다. \(k>n\)이면 값은 \(0\)이다.

첫 줄에 \(Q\) (\(1 \le Q \le 2000\))가 주어진다. 다음 \(Q\)개의 줄에는 각각 두 정수 \(n\)과 \(k\)가 주어진다 (\(0 \le n \le 2 \times 10^5\), \(0 \le k \le n+5\)).

각 질의에 대해 \(\binom{n}{k} \bmod (10^9+7)\)을 한 줄에 하나씩 출력한다.

riseoj 작성

출처 RiseOJ Basics