Problems
He`s Circles
He`s Circles
He wrote \textbf{n} letters "\textbf{X}" and "\textbf{E}" in a circle. He thought that there were \textbf{2^n} possibilities to do it, because each letter may be either "\textbf{X}" or "\textbf{E}". But Qc noticed that some different sequences of letters can be transformed one to another with a circular shift (thus representing actually the same circular string).
For example, strings "\textbf{XXE}"-"\textbf{XEX}"-"\textbf{EXX}" are actually the same.
Qc wants to know how many different circular strings of \textbf{n }letters exist. Help him to find that out.
\includegraphics{https://static.e-olymp.com/content/75/759f89af2a1a31ceaff916012a32025ecaf071b6.jpg}
\InputFile
The input file contains a single integer \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{200000}).
\OutputFile
Output a single integer -- the number circular strings of length \textbf{n}.
Input example #1
3
Output example #1
4