"Двоично Тегло" на едно число е броят единици, които то има в двоичния си запис. Например теглото на числото 42 е три, тъй като двоичното му представяне е 101010. 1337 от друга страна има тегло шест (двоичното му представяне е 10100111001).

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

Ели генерира числата по следния начин: в началото тя определя пет цели числа N, F, A, B, и M. Редицата има N члена, първият от които е F. Всеки следващ се образува, като предходният се умножи по A, после се прибави B и се вземе остатъка на резултата при деление на M. Тоест:

1. S₁ = F
2. S_i = (S_i-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 113	17
1337 7 17 9 12345	8837
12345678 123 41 2 1000000000	189462355