eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 0.1 seconds
Memory limit 64 MiB

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

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

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

Input data

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

Output data

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

Examples

Input example #1
5
Output example #1
4
Author Alexandr Burkov
Source Distance Summer Computer School - Summer 2013