Задачи
Васин круг
Васин круг
Вася выписал \textbf{n} букв "\textbf{X}" и "\textbf{E}" по кругу. Вася подумал, что получится \textbf{2^n} вариантов сделать это, так как каждая буква может быть либо "\textbf{X}", либо "\textbf{E}". Однако Петя заметил, что некоторые различные последовательности букв могут быть преобразованы друг в друга циклическим сдвигом (таким образом представляя одну и ту же циклическую строку).
Например, строки "\textbf{XXE}"-"\textbf{XEX}"-"\textbf{EXX}" на самом деле одинаковы.
Петя хочет знать, сколько существует различных циклических строк из \textbf{n }букв. Помогите ему это узнать.
\includegraphics{https://static.e-olymp.com/content/75/759f89af2a1a31ceaff916012a32025ecaf071b6.jpg}
\InputFile
Одно число \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{200000}).
\OutputFile
Вывести количество циклических строк длины \textbf{n}.
Входные данные #1
3
Выходные данные #1
4