Description

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

Input

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

Output

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

Sample

Input

3
10  3
100  0
29265  24150

Output

120
1
7698

Source: JiMoDi