Tính tổ hợp chập \(k\) của \(n\) phần tử \(C_n^k\) hay \(\dbinom{n}{k}\) theo modulo \(10^9+7\)

Input

• Một dòng duy nhất chứa \(2\) số nguyên \(n\) và \(k\) \((k < n < 10^{9} + 7)\)
  

Output

• Gồm \(1\) số nguyên không âm duy nhất là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^6\)
  
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 10^9+7\)
  

Example

1000000 500000

996692777