Нехай \textbf{S} - деяка множина цілих невід'ємних чисел. Побудуємо на ній послідовність \textbf{G_S}(\textbf{n}) (\textbf{n} > \textbf{0}) за наступною формулою \includegraphics{https://static.e-olymp.com/content/ac/ac3b0f821ca55e46296ccb37ddaab9609a243270.jpg} де \textbf{mex} \textbf{A} - найменше ціле невід'ємне число, яке не належить множині \textbf{A}, а \textbf{a} \textbf{xor} \textbf{b} - результат побітового додавання чисел \textbf{a} та \textbf{b} по модулю \textbf{2}. Будемо називати множину \textbf{S} доброю, якщо \textbf{G_S}(\textbf{n}+\textbf{4})=\textbf{G_S}(\textbf{n}) при \textbf{n} > \textbf{4}, а значення \textbf{G_S}(\textbf{n}) при \textbf{n}=\textbf{1},\textbf{2},\textbf{3},\textbf{4},\textbf{5},\textbf{6},\textbf{7},\textbf{8} рівні \textbf{0},\textbf{0},\textbf{0},\textbf{1},\textbf{0},\textbf{2},\textbf{1},\textbf{3} відповідно. Задано \textbf{n} ≥ \textbf{0}. Потрібно найти кількість добрих множин, елементи яких не перевищують \textbf{n}, по модулю \textbf{10^9}+\textbf{7}. \InputFile У єдиному рядку вхідного файлу задано ціле невід'ємне число \textbf{n} ≤ \textbf{10^18}. \OutputFile У єдиний рядок вихідного файлу виведіть відповідь до задачі.