Felies Fogg butun dunyoni 80 kunda aylanib chiqish oxirida samoliyotni yaratdi. Bir yil o’tgach esa barcha yerda samoliyotlar yurib turgach u o’z rekordini yangilamoqchi bo’ldi. Uning hisob-kitoblariga ko’ra agar samoliyotdan foydalansa berilgan masofani 2 marta tezroq bosib o’tish mumkin. U o’zining marshrutini belgilab oldi. Unga ko’ra u 0-stansiyadan yo’lga chiqib, 1, 2, ... n stansiyalar orqali o’tib, n-stansiyada o’z sayohatini yakunlaydi. Ya’ni i-yurishda i-1 – stansiyadan i – stansiyaga o’tishi kerak. Har bir i-yo’lni poyezd yoki kemada bosib o’tishi mumkin. Buning uchun unga a[i] vaqt kerak bo’ladi. Agar bu masofani samoliyotda bosib o’tsa a[i]/2 vaqtda bosib o’tish mumkin. Lekin Felies Fogg samoliyotdan juda ko’p foydalanishni istamadi. Shuning uchun u ko’pi bilan k marta samoliyotga chiqishga qaror qildi. Felies Fogg dunyoni iloji borischa tezroq aylanib chiqishni xoxlaydi. Stansiyalar soni esa yatarlicha ko’p. U har stansiyalar oralig’idagi masofalarni biladi. Lekin u olim bo’lsa ham stansiyalar soni yetarlicha ko’p bo’lganligi uchun qanday qilib eng kam vaqtda borishni hisoblash uning uchun qiyin. Unga buni hisoblashda yordam bering. Agar bu ishda yordam bersangiz Felies Fogg Pospartuning o’rniga sayohatga o’zi bilan sizni olib ketmoqchi.

Har bir qo’shni i va i-1 stansiyalar orasidagi poyezd yoki kemada bosib o’ish vaqti  a_i orqali ifodalanadi. a_i massiv elementlari qiymatlari butun sonlar a₁ ning qiymati ma’lum, i >1 lar uchun qiymatlari quyidagicha formula bo’yicha hisoblanadi:

a_i = (a_i-1*b+c) % m;

b, c, m – butun sonlar.

Kiruvchi ma’lumotlar

Birinchi qatorda n, k(1≤n≤10⁷, 0≤k≤10⁷) butun sonlari beriladi.  Ikkinchiq qatorda a₁, b, c, m(1≤a₁, b, c, m≤10⁹) butun sonlari beriladi.

Chiquvchi ma’lumotlar

Eng kam vaqt qiymatini 10^-1 aniqlikda chiqaring.

Misollar