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