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.