2209 - 计数count
Description

现在给你两个正整数 n 和 m,

请问有多少种整数方案 x1, x2, . . . xn 使得等式 x1 +x2 +x3 + · · · + xn = m 成立, 

这些数值必须要满足 0 ≤ x1 ≤ x2 ≤ x3 · · · ≤ xn 

例如 m = 3, n = 2, 共有 2 种方案,{0, 3}, {1, 2}, 答案可能很大,方案数对 10^8 + 7 取余 输出即可。

Input

第一行一个正整数 T, 表示数据组数 

接下来 T 行,每行两个正整数,分别为 m 和 n

Output

输出 T 行,每行为要求的答案

Examples

Input

2
3 2
7 3

Output

2
8
Hint

对于 10% 的数据,1 ≤ n ≤ m ≤ 10 

对于 30% 的数据,1 ≤ n ≤ m ≤ 50 

对于 50% 的数据,1 ≤ n ≤ m ≤ 100 

对于 100% 的数据,1 ≤ n ≤ m ≤ 300

题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 46
通过次数 29