Пусть \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 В единственную строку выходного файла выведите ответ на задачу.