描述

相信大家对组合数一定很了解吧！这个问题很简单，就是给出C(N,M)的形式，求出这个组合数的值。

格式

输入格式

输入第一行是一个整数t，表示一共要求几个组合数，接下来t行每行两个整数(n,m. 0<=M<N<2^31)。

输出格式

每行一个整数表示该组合数的值，由于可能求出来的结果很大，所以只要给出模10007以后的结果就行。

样例1

样例输入1

3
10  3
100  0
29265  24150

样例输出1

120
1
7698

限制

1000ms
32768KB

提示

来源

JiMoDi