D. Лиса и идеальные наборы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Лиса Сиель изучает теорию чисел.

Она считает, что непустое множество S, состоящее из неотрицательных целых чисел, является идеальным тогда и только тогда, когда для любых (a может равняться b), . Где операция xor означает операцию исключающего ИЛИ (http://ru.wikipedia.org/wiki/Сложение_по_модулю_2).

Пожалуйста, вычислите количество идеальных множеств, состоящих из целых чисел, не превосходящих k. Ответ может получиться достаточно большим, поэтому выведите его по модулю 1000000007 (109 + 7).

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

В первой строке записано целое число k (0 ≤ k ≤ 109).

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

Выведите единственное целое число — количество искомых множеств по модулю 1000000007 (109 + 7).

Примеры
Входные данные
1
Выходные данные
2
Входные данные
2
Выходные данные
3
Входные данные
3
Выходные данные
5
Входные данные
4
Выходные данные
6
Примечание

В первом тестовом примере существует 2 таких множества: {0} и {0, 1}. Обратите внимание, что {1} не является идеальным множеством, так как 1 xor 1 = 0 и {1} не содержит нулей.

В четвертом примере существует 6 таких множеств: {0}, {0, 1}, {0, 2}, {0, 3}, {0, 4} и {0, 1, 2, 3}.