Nhiệm vụ của bạn là tính toán \(n\) hệ số nhị thức chia lấy dư cho \(10^9+7\).

Một hệ số nhị thức \(\binom{a}{b}\) có thể được tính toán bằng công thức \(\frac{a!}{b!(a-b)!}\). Chúng ta giả định rằng \(a\) và \(b\) là những số nguyên và \(0 \leq b \leq a\).

Input

• Dòng đầu vào đầu tiên chứa một số nguyên \(n\): số lượng tính toán.
• Sau này, có \(n\) dòng, mỗi dòng chứa hai số nguyên \(a\) và \(b\).

Output

• In mỗi hệ số nhị thức chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

• \(1 \leq n \leq 10^5\)
• \(0 \leq b \leq a \leq 10^6\)

Example

Sample input

3
5 3
8 1
9 5

Sample output

10
8
126