Игра 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.

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

В единственную строку выходного файла выведите ответ на задачу.

Примеры