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}.