\includegraphics{https://static.e-olymp.com/content/ed/ed2bf96703312b62ae97758daf4bba592e933f5b.jpg} Недавно Буратино узнал про такую структуру данных, как дерево отрезков. Более точно дерево отрезков представляет собой бинарное дерево, каждая вершина которого содержит некоторую информацию об отрезке с границами \textbf{\[l; r\]}. Корнем дерева является вершина, которая содержит в себе информацию о всей последовательности \textbf{\[1; N\]}, где \textbf{N} -- длина последовательности. Для остальных вершин справедливо следующее: если \textbf{l} равно \textbf{r}, то это вершина листовая, иначе у нее есть ровно два потомка, которые содержат информацию об отрезках \textbf{\[l; m\]} и \textbf{\[m+1, r\]} соответственно. Наиболее эффективным дерево отрезков будет в случае, когда длина отрезков \textbf{\[l; m\]} и \textbf{\[m+1, r\] }равны. Однако, в случае, когда длина исходного отрезка \textbf{\[l; r\]} нечетная, на два равных отрезка исходный разбить нельзя. В этом случае левый или правый отрезок будет на единицу длиннее второго. После каждого выступления Буратино рисует некоторое дерево отрезков для массива длиной \textbf{N}. При чем каждый раз он случайно выбирает левый или правый отрезок сделать длиннее, при невозможности сделать их равными. Ваша задача посчитать, сколько различных деревьев сможет нарисовать Буратино. \InputFile В единственной строке находится число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{2·10^9}) -- размер массива, по которому Буратино будет строить дерево отрезков. \OutputFile В единственной строке выведите количество различных деревьев, которые может построить Буратино. Так как ответ может быть очень большим, выведите его по модулю \textbf{10^9+7}.