ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1862. Очень состоятельный крот

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
— Чем хотите пока заняться, состоятельные кроты?
— А что если нам посчитать?
— И то дело!
Один очень состоятельный крот знает только целые неотрицательные числа. Он умеет выполнять на своих счётах три действия:
  1. получать из числа x число 2x;
  2. получать из числа x число 2x + 1;
  3. получать из числа x число ⌊x/2⌋ (целую часть при делении x пополам).
Каждое утро крот выбирает очередную пару целых чисел x и y, таких что 1 ≤ x < y ≤ 2l − 1, и в течение дня получает из числа x число y, выполняя на своих счётах некоторую последовательность действий. Крот хорошо умеет считать, поэтому всегда обходится самой короткой последовательностью действий, достаточной для получения числа y из числа x.
Сколько в общей сложности действий на счётах выполнит крот, пока не переберёт все пары чисел в диапазоне от 1 до 2l − 1?

Исходные данные

В единственной строке записано целое число l (2 ≤ l ≤ 1018).

Результат

Найдите количество действий на счётах, которое должен будет выполнить крот, и выведите остаток при делении этого числа на 109 + 7.

Пример

исходные данныерезультат
2
4

Замечания

В первый день крот получит из числа 1 число 2, выполнив первое действие. Во второй день он получит из числа 1 число 3, выполнив второе действие. В третий день он получит из числа 2 число 3, выполнив сначала третье, а затем второе действие.
Автор задачи: Денис Дублённых
Источник задачи: Открытый командный чемпионат УрФУ по программированию — 2011