Ngân hàng câu hỏi của trường SuperKids có \(10^9\) bài toán đánh số từ \(1\) tới \(10^9\), bài toán thứ \(i\) có độ khó là \(i\). Giáo sư \(X\) muốn chọn \(k\) bài toán khác nhau trong số đó để làm một đề thi sao cho tổng độ khó của các bài toán được chọn đúng bằng \(n\). Hãy cho biết giáo sư \(X\) có bao nhiêu cách chọn.

(Hai cách chọn được gọi là khác nhau nếu có một bài toán được chọn trong một cách nhưng không được chọn trong cách còn lại)

Input

• Dòng đầu tiên chứa một số nguyên dương \(T \leq 10\) là số test
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(k, n\) \((k \leq 10; n \leq 10^9)\) ứng với một test

Output

• Ứng với mỗi test, in ra một số nguyên duy nhất trên một dòng là số dư của kết quả tìm được khi chia cho \(1000000007\) \((10^9 + 7)\)

Example

2
3 10
2 8

4
3