从 i 个不同元素中选出 j 个元素，得到一个集合，方案数量记为 C_i^j。

只要选出的元素相同，就视为同一种方案，选择的先后顺序不产生新方案。约定从 0 个元素中选出 0 个元素有 1 种方案。

给定 q 个询问，每次给出 i,j，请输出 C_i^j 对 1000000007 取模的结果。各个询问相互独立。

第一行包含一个正整数 q，表示询问数量。

接下来 q 行，每行包含两个非负整数 i,j，表示一次询问。

按照询问顺序输出 q 行，每行一个整数，表示对应询问的答案。

样例 1 解释

• 从 0 个元素中选 0 个，只有空集这 1 种方案。
• 对四个元素 1,2,3,4，选出两个元素的集合为 {1,2}、{1,3}、{1,4}、{2,3}、{2,4}、{3,4}，共有 6 种。
• 从五个元素中选一个，有 5 种；选出全部五个，只有 1 种。
• 从六个元素中选三个，有 20 种。

样例 2 解释

本例包含选取数量互补的询问，以及需要取模的较大组合数。输出取模后的结果。

样例 3

见题目目录下的 comb/3.in 与 comb/3.ans。

该样例满足测试点 3,4 的约束条件。

样例 4

见题目目录下的 comb/4.in 与 comb/4.ans。

该样例满足测试点 7\sim10 的约束条件。

数据范围

对于所有测试数据，保证 1\le q\le10000，每个询问满足 0\le j\le i\le2000。

本题共 10 个测试点，每个测试点 10 分。

组合数学组合数