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 đó, có \(n\) dòng, mỗi dòng chứa hai số nguyên \(a\) và \(b\)

Constraints

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

Output

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

Example

3
5 3
8 1
9 5

10
8
126