测试数据来自 system/3038

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　将自然数 1 到 \(n\) 任意排列，然后在排列的每两个数之间根据他们的大小关系插入“ >”和“ <”。例如：对于 1..5 的一个排列： 3 2 4 1 5，可得到： 3 > 2 < 4 > 1 < 5，其中有两个 > 和两个 <。

　　现在给出自然数 \(n\)， 问在自然数 \(1..n\) 的所有排列中，有多少个排列恰好有 \(k\) 个 <。

【输入格式】

　　第一行一个整数 \(T\)，表示有 \(T\) 组数据。每组数据的占一行，包含两个整数 \(n\) 和 \(k\)，它们之间用一个空格分开。

【输出格式】

　　每组数据输出一行，每行一个整数，表示对应输入的排列数，这个数如果很大，则需要输出 mod 1000000007 的结果。

【输入输出样例】

　Input

4
5 2
8 1
9 4
7 3

　Output

66
247
156190
2416

【测试点性质】

　　对于 \(30\%\) 的数据，\(n≤10\)。
　　对于 \(100\%\) 的数据，\(k<n≤1000\)。

【来源】

　　Mr.he