#2982. combination

题目描述

LMZ 有 n 个不同的基友，他每天晚上要选 m 个进行 [ 河蟹 ] ，而且要求每天晚上的选择都不一样。那么 LMZ 能够持续多少个这样的夜晚呢？当然， LMZ 的一年有 10007 天，所以他想知道答案 mod 10007 的值。 (1 <=m<=n<=200,000,000)

输入格式

** **第一行一个整数 t ，表示有 t 组数据。 (t <=200)

** **接下来 t 行每行两个整数 n, m ，如题意。

输出格式

T 行，每行一个数，为 C(n, m) mod 10007 的答案。

样例

样例输入

4  

5 1  

5 2  

7 3  

4 2  

样例输出

5  

10  

35  

6

数据范围与提示