\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}.