~/algor $ cat masalalar/kombinatorika-c-n-k
Kombin-02
Binomial koeffitsiyent so'rovlari
Muallif:
Iqbolshoh Ilhomjonov
O'rtacha
1000 ms
128 MB
45%
$q$ ta so'rov berilgan, har birida butun sonlar $n$ va $k$. $n$ ta narsadan $k$ tasini tanlash usullari soni
$$C_{n}^{k} = \frac{n!}{k! * (n - k)!}$$
ni toping ($k \gt n$ bo'lsa, $C_{n}^{k} = 0$).
Kiruvchi ma'lumotlar
Birinchi qatorda natural son $q$. Keyingi $q$ ta qatorning har birida ikkita butun son: $n$ va $k$.
Chiquvchi ma'lumotlar
Har bir so'rov uchun alohida qatorda bitta butun son — $C_{n}^{k}$ ning $10^{9} + 7$ ga bo'lgandagi qoldig'i.
Izoh
$1 \le q \le 10^{5}$
$0 \le n \le 10^{6}$
$0 \le k \le n + 2$
Misollar
Kirish #1
3 5 2 10 0 4 4
Chiqish #1
10 1 1
Kirish #2
2 6 3 3 5
Chiqish #2
20 0