toys

След приключване на едно парти, приятелите на Гигел трябва да пренесат от хола всичките му играчки до неговата стая. За да се отиде от хола до стаята на Гигел, трябва да се измине разстояние L. Гигел има N приятеля (номерирани от 1 до N) и M играчки, които трябва да се преместят. Приятелите на Гигел започват да пренасят играчките и някои деца се движат от хола към стаята на Гигел с играчка в ръце, други се връщат обратно, за да вземат следваща играчка.

Ще идентифицираме позицията на всяко дете по пътя му по следния начин: За всяко дете i дефинираме две стойности, di и ti, със следния смисъл: di задава разстоянието, на което детето i се е отдалечило от стаята на Гигел и ti=1, когато детето i пренася играчка от хола към стаята на Гигел, и съответно ti=0, когато детето се връща от стаята на Гигел към хола без играчка.

Всяко дете взема една играчка от хола, пренася я в стаята на Гигел и се връща обратно да вземе следваща играчка. Това се повтаря многократно, докато всичките играчки бъдат преместени.

Гигел анализира конфигурациата на N-те свои приятели и забелязва, че d1=S и t1=1 (т.е. първото дете е на разстояние S от стаята на Гигел и пренася играчка). За останалите деца (i=2, 3, ..., N) стойностите di и ti могат да бъдат намерени чрез следните формули, където X, Y, Z и V са известни:
di = ( X * di-1 + Y * ( i - 1 ) ) % ( L - 1 ) + 1
ti = ( Z * di-1 + V * ( i - 1 ) ) % 2
Тук чрез
a % b е означен остатъкът при на делението на  a с  b.

Задача

Помогнете на Гигел да намери минималното време, за което всичките играчки могат да бъдат върнати в неговата стая.

Вход

Първият ред на входния файл toys.in съдържа трите цели положителни числа: N, L и M, разделени с интервали. Следващият ред съдържа петте цели положителни числа: S,X,Y,Z,V, разделени с интервали.

Output Data

Файлът toys.out трябва да съдържа един ред с търсената минимална стойност.

Ограничения

  • 1 <= M <= 2 000 000 000
  • 0 <= N <= 2 000 000
  • 0 <= L <= 2 000 000
  • 0 <= X, Y, Z, V <= 2 000 000
  • 0 <= S <= L
  • Резултатът се вмества в 64 битов целочислен тип.
  • Всяко дете при движението си изминава една единица разстояние за една единица време и времето за вземане и за поставяне на играчка е пренебрежимо малко.

Пример

toys.in

toys.out

Обяснение

5 101 100
84 89 79 17 97

4124

Има 5 деца, дължината на пътя е 101 и броят на играчките е 100. Началната конфигурация на децата е:
d1= 84 t1=1
d2=(89*84+79*1)%100+1=56 t2=(17*84+97*1)%2=1
d3=(89*56+79*2)%100+1=43 t3=(17*56+97*2)%2=0
d4=(89*43+79*3)%100+1=65 t4=(17*43+97*3)%2=0
d5=(89*65+79*4)%100+1=2  t5=(17*43+97*4)%2=1

  Време за работа на програмата: 0.2 секунди за тест

Diaconu Adrian Paul
University of Bucharest, Mathematics & IT Department
ditzone@gmail.com

Превод на български: Емил Келеведжиев