eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 0.1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
5
Çıxış verilənləri #1
4
Müəllif Александр Бурков
Mənbə Дистанционная Летняя Компьютерная Школа - лето 2013 года