Popcounts
Турнир за Купата на Декана, 2011
Time Limit: 0.5s, Memory Limit: 64MiB
"Двоично Тегло" на едно число е броят единици, които то има в двоичния си запис. Например теглото на числото 42 е три, тъй като двоичното му представяне е 101010. 1337 от друга страна има тегло шест (двоичното му представяне е 10100111001).

Ели генерира случайни числа и смята сумата на техните двоични тегла. Защо тя прави това не е ясно, но все пак вие решавате да я впечатлите, като напишете програма, която бързо смята тази сума.

Ели генерира числата по следния начин: в началото тя определя пет цели числа N, F, A, B, и M. Редицата има N члена, първият от които е F. Всеки следващ се образува, като предходният се умножи по A, после се прибави B и се вземе остатъка на резултата при деление на M. Тоест:
  1. S1 = F
  2. Si = (Si-1 * A + B) % M, за i = 2, 3, ..., N.
Гореописаната процедура се нарича Linear Congruential Generator (LCG) и е един от най-старите и разпространени начини за генериране на псевдослучайни числа.
Вход
На единствен ред на стандартния вход ще бъдат зададени петте цели числа N, F, A, B, и M.
Изход
На стандартния изход изведете едно единствено цяло число – сумата на двоичните тегла на генерираните числа.
Ограничения
  • 1 ≤ N ≤ 20,000,000
  • 0 ≤ F, A, B < M ≤ 1,000,000,007
Примерен Вход Примерен Изход
5 42 3 5 11317
1337 7 17 9 123458837
12345678 123 41 2 1000000000189462355
В първия пример генерираните числа са 42, 18, 59, 69, и 99. Техните двоични тегла са съответно 3, 2, 5, 3, и 4, които дават сума 17.
Мрън!