Генератор псевдовипадкових чисел

Дональд захоплюється природою. Як програміст, він створює програми для моделювання росту дерев або побудови реалістичних тривимірних ландшафтів. Для цього йому потрібен надійний генератор псевдовипадкових чисел. Дональд розробив такий метод для генерування нескінченної послідовності 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).

Приклади