Hãy trả lời \(t\) câu hỏi có nội dung như sau: Hãy tính chỉnh hợp chập \(k\) của \(n\), tức \(A_n^k\).

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(t\) \((t \leq 10^5)\).
• \(t\) dòng tiếp theo, mỗi dòng gồm hai số \(n\) và \(k\) \((k \leq n)\)

Định dạng đầu ra

• In ra \(t\) dòng là đáp án chia lấy dư cho \(10^9+7\)

Điểm số

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 20\)
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 1000\)
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 10^6\)

Ví dụ

1
5 3

60