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.