이항 계수와 쿼리

자연수 $N$과 정수 $K$로 이루어진 쌍이 $M$개 주어진다. 각 쌍마다 이항 계수 $\binom{N}{K}$를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 쌍의 개수 $M$이 주어진다. ($1 \le M \le 100{,}000$)

둘째 줄부터 $M$개의 줄에 각 쌍의 $N$과 $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 4{,}000{,}000$, $0 \le K \le N$)

$M$개의 줄에 각 쌍의 $\binom{N}{K}$를 1,000,000,007로 나눈 나머지를 입력 순서대로 출력한다.