Золотий ключик або пригоди Буратіно#4494
Нещодавно Буратіно відкрив для себе структуру даних, відому як дерево відрізків.
Дерево відрізків — це, по суті, бінарне дерево, в якому кожна вершина містить інформацію про відрізок, визначений межами [l; r]. Коренева вершина представляє всю послідовність , де — довжина цієї послідовності. Для будь-якої іншої вершини виконується наступне: якщо l = r, то вершина є листком. Інакше вона має рівно двох дітей, які містять інформацію про відрізки та [m+1, r] відповідно. Дерево відрізків є найефективнішим, коли відрізки та [m+1, r] мають однакову довжину. Проте, якщо відрізок [l; r] має непарну довжину, то його неможливо розбити на дві рівні частини. У такому випадку або лівий, або правий відрізок буде на один елемент більшим за інший. Після кожної вистави Буратіно будує дерево відрізків для масиву довжини . Кожного разу він випадковим чином вирішує, робити довшим лівий чи правий відрізок, якщо рівний поділ неможливий.
Ваше завдання — визначити, скільки різних дерев відрізків може створити Буратіно.
Вхідні дані складаються з одного рядка, який містить число (1 \leq N \leq 2 \cdot 10^9) — розмір масиву, для якого Буратіно буде будувати дерево відрізків.
Виведіть єдине число — кількість різних дерев, які може побудувати Буратіно. Оскільки відповідь може бути дуже великою, виведіть її за модулем 10^9+7.
Приклад 1