Дональд любит природу. Будучи программистом, Дональд пишет программы для имитации роста деревьев или построения реалистичных трехмерных ландшафтов. Для этого Дональду нужен хороший генератор псевдослучайных чисел. Он изобретает следующий метод для создания бесконечной последовательности 40-битных целых чисел без знака.
В последней строке x >> 20 обозначает частное от евклидова деления x на 2^20
, а x % m обозначает остаток от евклидова деления x на m.
В качестве самого первого теста, чтобы решить, действительно ли это хороший генератор псевдослучайных чисел, Дональд хочет подсчитать количество четных значений, произведенных этой последовательностью, чтобы проверить, достаточно ли оно близко к 50%. Ваша помощь будет приветствоваться.
Одно целое число n (0 ≤ n < 2^63
).
Выведите одну строку с одним целым числом, соответствующим количеству четных значений в последовательности S(0), S(1), ..., S(n - 1).