Let \textbf{S} - is a certain set of nonnegative integers. Let us construct a sequence \textbf{G_S}(\textbf{n}) (\textbf{n} > \textbf{0}) using the formula \includegraphics{https://static.e-olymp.com/content/ac/ac3b0f821ca55e46296ccb37ddaab9609a243270.jpg} where \textbf{mex} \textbf{A} - is the least nonnegative integer which does not belong to the set \textbf{A}, and \textbf{a} \textbf{xor} \textbf{b} - is a result of bitwise addition of numbers \textbf{a} and \textbf{b} modulo \textbf{2}. A set \textbf{S} well be called beautiful, if \textbf{G_S}(\textbf{n}+\textbf{4})=\textbf{G_S}(\textbf{n}) when \textbf{n} > \textbf{4}, and values \textbf{G_S}(\textbf{n}) are equal \textbf{0},\textbf{0},\textbf{0},\textbf{1},\textbf{0},\textbf{2},\textbf{1},\textbf{3} when \textbf{n}=\textbf{1},\textbf{2},\textbf{3},\textbf{4},\textbf{5},\textbf{6},\textbf{7},\textbf{8} correspondingly. You are given \textbf{n} ≥ \textbf{0} and required to find the number of beautiful sets with elements not exceeded \textbf{n}, and yields this number modulo\textbf{10^9}+\textbf{7}. \InputFile The only line of thei nput file contains a nonnegative integer \textbf{n} ≤ \textbf{10^18}. \OutputFile In the output file you should write the answer of the task.