Гра S-Грюнді

Нехай S - деяка множина цілих невід'ємних чисел. Побудуємо на ній послідовність G_S(n) (n > 0) за наступною формулою

де mex A - найменше ціле невід'ємне число, яке не належить множині A, а a xor b - результат побітового додавання чисел a та b по модулю 2.

Будемо називати множину S доброю, якщо G_S(n+4)=G_S(n) при n > 4, а значення G_S(n) при n=1,2,3,4,5,6,7,8 рівні 0,0,0,1,0,2,1,3 відповідно.

Задано n ≥ 0. Потрібно найти кількість добрих множин, елементи яких не перевищують n, по модулю 10^9+7.

Вхідні дані

У єдиному рядку вхідного файлу задано ціле невід'ємне число n ≤ 10^18.

Вихідні дані

У єдиний рядок вихідного файлу виведіть відповідь до задачі.

Приклади