Tính tổ hợp chập k của n


Submit solution

Points: 3
Time limit: 3.0s
Memory limit: 98M

Author:
Problem type

Cho số nguyên dương \(n\) và cho số tự nhiên \(k\) nằm trong đoạn \([0,n]\) Hãy tính tổ hợp chập \(k\) của \(n\)

Input

Dòng đầu là số bộ test \(t (1 \le t \le 10) \)

Tiếp theo \(t\) dòng mỗi dòng chứa hai số \(k\) và \(n\) thỏa mãn \((0 \le k \le n \le 10^5)\)

Output

Kết quả tổ hợp chập \(k\) của \(n\) bởi vì kết quả quá lớn chỉ cần lấy phần dư của kết quả chia cho \(10^9+7\)

Ví dụ

Input

4
6 3
10 7
41 21
20 17

Output

20
120
128935337
1140
tichpx

Comments


  • 0
    TICHPX  commented on June 22, 2020, 2:50 a.m.

    Chắc phải làm thêm bài "lại là tổ hợp chập" nữa nhỉ