Stories
Национална Олимпиада по Информатика 2017, Кръг 2
Time Limit: 0.7s, Memory Limit: 128MiB
Всеки ден Ели иска да бъде център на вниманието в училище. Затова тя разказва на всички най-забавната история, която й се е случила през последните (до) K дни. След като минат те, тя спира да я разказва, тъй като вече достатъчно много хората са я слушали. Разбира се, ако през някой от дните й се случи по-интересна случка, тя започва да разказва нея още в деня, в който й се е случила.

Всяка история може да бъде оценена с цяло неотрицателно число Ai – колко забавна е била тя. История със стойност 0 е доста скучна, докато такава с голямо число е много смешна.

Завършвайки училище, Ели се чуди дали ще я запомнят като забавно момиче. Сега тя иска да определи сумарно колко забавна е била в период от N дни. С други думи, тя иска да намери сумата на забавността на разказаните истории във всеки един от дните. Забележете, че в дни 1, 2, ... K-1 тя избира най-забавната сред по-малко от K истории.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и K – броя дни, в които Ели е разказвала истории, и колко стара може да бъде историята. На втория ред ще бъдат зададени целите числа FIRST, MUL, ADD, MOD. В първия ден на момичето й се е случило случка със забавност A1 = FIRST. Във всеки следващ ден й се е случила случка със забавност Ai = (Ai-1 * MUL + ADD) % MOD.
Изход
На единствен ред на стандартния изход изведете едно цяло число – сумата от забавността на разказаните истории през всички N дни.
Ограничения
  • 1 ≤ КN ≤ 10,000,000
  • 0 ≤ FIRST, MUL, ADD < MOD ≤ 1,000,000,007
Примерен Вход Примерен Изход
7 3 5 3 2 23 79
133742 666 20 3 17 1000000007 133403869908674
В първия пример Ели разглежда 7 дни, като всяка история може да бъде разказана не по-късно от 3 дни след като се е случила. Случките, които са се случили, са със забавност, съответно, 5, 17, 7, 0, 2, 8, и 3. В първия ден тя разказва единствената, която й се е случила до сега – тази със стойност 5. Във втория й се случва по-забавна история (със стойност 17), която разказва във втория, третия, и четвъртия ден. На петия ден тя все още е най-забавната, която й се е случила, но вече е твърде стара, затова момичето разказва следващата най-забавна – тази със стойност 7. На шестия ден й се случва по-забавна, със стойност 8, която разказва и на последния ден. Сумата на забавността на историите е 5 + 17 + 17 + 17 + 7 + 8 + 8 = 79.
Мрън!