Migrated from Lutece 1723 篝火晚会

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

京州电子科技大学60周年校庆就要到了，当天将举行盛大的篝火晚会。篝火晚会上会点燃K个篝火，为了避免看起来浪费能源，每个篝火都会被至少一名同学使用，由于你没有任何的空间感，你认为这K个篝火之间没有任何区别。作为学生会长，你负责给N名同学安排好他们应该坐在哪个篝火旁边。那么问题来了，当天有多少种安排篝火晚会的方式呢。

Input

第一行输入数据组数T 对于每组数据，在一行输入两个数N,K，学生数，篝火数 1 <= T <= 1000 1 <= K <= N <=1000

Output

对于每组数据，输出一个数，安排方式的种类数，由于数字可能比较大，你需要输出这个数对1e9+7取模的结果

Samples

1
3 2

3

Note

对于样例，设有3个同学，A，B，C 则三种方式为 1.(A，B) (C) 2.(B, C) (A) 3.(A, C) (B)

Resources

2017 UESTC Training for Math