Description

Original source: BZOJ 2982

LMZ has $n$ distinct friends, and every night he selects $m$ of them for [censored], ensuring that each night's selection is different. How many such nights can LMZ sustain? Note that LMZ's year consists of $10007$ days, so he wants to know the answer modulo $10007$.

Input Format

The first line contains an integer $t$, indicating the number of test cases.

Each of the next $t$ lines contains two integers $n$ and $m$, as described in the problem statement.

Output Format

Output $t$ lines, each containing a single number, which is the value of $\binom{n}{m} \bmod 10007$.

Sample 1

4
5 1
5 2
7 3
4 2

5
10
35
6

Data Range and Hints

For all test cases, $1\le t\le 200$, $1\le m\le n\le 2\times 10^8$.