Tổ hợp Ckn 2

Xem PDF

Điểm: 1800 (p) Thời gian: 1.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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\)\(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

Test 1

Input
1000000 500000
Output
996692777

Bình luận