eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Золотой ключик или приключения Буратино

Золотой ключик или приключения Буратино

Лимит времени 0.1 секунд
Лимит использования памяти 64 MiB

Недавно Буратино узнал про такую структуру данных, как дерево отрезков.

Более точно дерево отрезков представляет собой бинарное дерево, каждая вершина которого содержит некоторую информацию об отрезке с границами [l; r]. Корнем дерева является вершина, которая содержит в себе информацию о всей последовательности [1; N], где N – длина последовательности. Для остальных вершин справедливо следующее: если l равно r, то это вершина листовая, иначе у нее есть ровно два потомка, которые содержат информацию об отрезках [l; m] и [m+1, r] соответственно. Наиболее эффективным дерево отрезков будет в случае, когда длина отрезков [l; m] и [m+1, r] равны. Однако, в случае, когда длина исходного отрезка [l; r] нечетная, на два равных отрезка исходный разбить нельзя. В этом случае левый или правый отрезок будет на единицу длиннее второго. После каждого выступления Буратино рисует некоторое дерево отрезков для массива длиной N. При чем каждый раз он случайно выбирает левый или правый отрезок сделать длиннее, при невозможности сделать их равными.

Ваша задача посчитать, сколько различных деревьев сможет нарисовать Буратино.

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

В единственной строке находится число N (1N2·10^9) – размер массива, по которому Буратино будет строить дерево отрезков.

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

В единственной строке выведите количество различных деревьев, которые может построить Буратино. Так как ответ может быть очень большим, выведите его по модулю 10^9+7.

Пример

Входные данные #1
5
Выходные данные #1
4
Автор Александр Бурков
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года