Генератор псевдослучайных чисел

Дональд любит природу. Будучи программистом, Дональд пишет программы для имитации роста деревьев или построения реалистичных трехмерных ландшафтов. Для этого Дональду нужен хороший генератор псевдослучайных чисел. Он изобретает следующий метод для создания бесконечной последовательности 40-битных целых чисел без знака.

m := 1 << 40 // = 2^40 = 1 099 511 627 776
S(0) := 0x600DCAFE // = 1 611 516 670
S(n + 1) := (S(n) + (S(n) >> 20) + 12345) % m

В последней строке x >> 20 обозначает частное от евклидова деления x на 2^20, а x % m обозначает остаток от евклидова деления x на m.

В качестве самого первого теста, чтобы решить, действительно ли это хороший генератор псевдослучайных чисел, Дональд хочет подсчитать количество четных значений, произведенных этой последовательностью, чтобы проверить, достаточно ли оно близко к 50%. Ваша помощь будет приветствоваться.

Входные данные

Одно целое число n (0 ≤ n < 2^63).

Выходные данные

Выведите одну строку с одним целым числом, соответствующим количеству четных значений в последовательности S(0), S(1), ..., S(n - 1).

Примеры