Tính tổ hợp modulo lớn

Buổi 58 — Modular Arithmetic Buổi 69-70 — Mock Tổng hợp Mathematics
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho $Q$ truy vấn, mỗi truy vấn gồm hai số nguyên $N, K$ ($0 \le K \le N \le 10^6$). Hãy tính giá trị tổ hợp chập $K$ của $N$ phần tử: $\binom{N}{K} \bmod (10^9 + 7)$.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $Q$.
  • $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $N, K$.
Dữ liệu ra

In ra $Q$ dòng, mỗi dòng là giá trị $\binom{N}{K} \bmod (10^9 + 7)$.

Ví dụ
Input Output
3
5 2
10 0
1000 500
10
1
159835829
Giới hạn

$1 \le Q \le 10^5$, $0 \le K \le N \le 10^6$.

Draft saved