Trong bài toán tổ hợp, hệ số tổ hợp chập \(k\) của \(n\) phần tử, ký hiệu là \(\binom{n}{k}\), xuất hiện rất phổ biến trong các bài toán đếm cấu hình. Khi các số \(n\) và \(k\) rất lớn, việc tính toán giá trị giai thừa trực tiếp sẽ gây ra hiện tượng tràn số.

Hãy lập trình tính giá trị \(\binom{n}{k} \pmod{10^9+7}\).

Định dạng đầu vào

• Một dòng duy nhất chứa hai số nguyên \(n, k\) cách nhau bởi dấu cách (\(0 \le k \le n \le 10^6\)).

Định dạng đầu ra

• In ra giá trị của \(\binom{n}{k} \pmod{10^9+7}\).

Ví dụ

Input:

5 2

Output:

10

Ràng buộc

• 30% số điểm ứng với \(n \le 1000\).
• 70% số điểm còn lại không có ràng buộc gì thêm.