Cho hai số nguyên \(n\) và \(k\). Hãy tính \(\displaystyle \binom{n}{k}\).

Input

• Một dòng duy nhất chứa hai số nguyên \(n\) và \(k\).

Output

• Một dòng duy nhất chứa một số nguyên là phần dư của đáp án khi chia cho \(10 ^ 9 + 7\).

Constraints

• \(0 \leq k \leq n \leq 10^{18}\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^3\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^6\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 10^9\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 2

10