Category
Similar Problems
0989. Binomial koeffitsientlar 3
Time limit : 5000 ms
Memory limit : 128 mb
Sizga $q$ ta so'rov berilgan. Har bir so'rovda sizga $n$ va $k$ sonlari berilgan va sizdan $C_n^k$ topish so'raladi. Javob tariqasida barcha so'rovlarga javobni $m$ bo'yicha qoldiqini chiqaring. Kiruvchi ma'lumotlar generatsiya orqali topiladi. So'rovlar ushbu formula orqali ifodalanadi.
$n_i = (943 * n_{i-1} + 17) \: mod \: 25000 + 1$
$k_i = (1999 * k_{i-1} + 24) \: mod \: 25000 + 1$
Birinchi so'rov sifatida berilgan $n_1$ va $k_1$ larni oling.
Kiruvchi ma’lumotlar
Birinchi qatorda 4 ta natural son, $q, n_1, k_1, m(1 \le n, k \le 25000)(1 \le q \le 10^7)(1 \le m \le 10^9)$.
Chiquvchi ma’lumotlar
Yagona qatorda masala yechimini chiqaring. Javob katta bo'lib ketishi mumkin, shuning uchun uni $m$ ga bo'lgandaki qoldiqini chiqaring.
Input |
---|
5 1 1 1001 |
Output |
273 |
Input |
---|
10000000 2501 6335 119216726 |
Output |
79501140 |