Binomial coefficient queries

You are given $M$ pairs, each made of a positive integer $N$ and an integer $K$. For every pair, compute the binomial coefficient $\binom{N}{K}$ modulo 1,000,000,007.

The first line contains the number of pairs $M$ ($1 \le M \le 100{,}000$).

Each of the next $M$ lines contains $N$ and $K$, separated by a space ($1 \le N \le 4{,}000{,}000$, $0 \le K \le N$).

Print $M$ lines. On the $i$-th line, print $\binom{N}{K}$ modulo 1,000,000,007 for the $i$-th pair, in input order.