Hệ số nhị thức

Bạn được giao nhiệm vụ tính toán hiệu quả \(n\) hệ số nhị thức \(\binom{a}{b}\) modulo \(10^9+7\).
Hệ số nhị thức \(\binom{a}{b}\) có thể được tính bằng công thức \(\frac{a!}{b!(a-b)!}\).
Chúng ta giả định rằng \(a\) và \(b\) là các số nguyên và \(0 \le b \le a\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 10^5\)), là số lượng phép tính.
• Tiếp theo là \(n\) dòng, mỗi dòng chứa hai số nguyên \(a\) và \(b\) (\(0 \le b \le a \le 10^6\)).

Output

• In ra mỗi hệ số nhị thức \(\binom{a}{b}\) modulo \(10^9+7\).

Example

3
5 3
8 1
9 5

10
8
126

Scoring

• Subtask \(1\) (\(50\%\) số điểm) : \(b \leq a \leq 5000\).
• Subtask \(2\) (\(50\%\) số điểm) : không có ràng buộc gì thêm.