Question

[Causdrubik Kiệt]

Sum
Input file: sum.inp
Output file: sum.out
Time limit: 1 seconds
Memory limit: 256 mebibytes
Đếm số cách chọn các số nguyên dương x₁, x₂, ..., x_n sao cho

\(\overset{n}{\overset{\Sigma}{1}}\) =s
với S là một số cho trước.
Input

· Dòng đầu tiên gồm số t, tức số test (1 ≤ t ≤ 10⁵).

· t dòng tiếp theo, mỗi dòng chứa 2 số n và S (1 ≤ n, S ≤ 100 000).

Output

· Với mỗi test, in ra số cách chọn, modulo 1 000 000 007.

Examples

sum.inp	sum.out
2 1 1000 2 3	1 2

ngôn ngữ C++