Binomial coefficient queries

Given M pairs N and K, print the binomial coefficient C(N, K) modulo 1,000,000,007.

Medium5CombinatoricsMathPrefix sumNo attempts yetTime limit1sMemory limit512 MB

Description

Examples1

Problem

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.

Input

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$ ).

Output

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.