He wrote n letters "X" and "E" in a circle. He thought that there were 2^n possibilities to do it, because each letter may be either "X" or "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 "XXE"-"XEX"-"EXX" are actually the same.
Qc wants to know how many different circular strings of n letters exist. Help him to find that out.
The input file contains a single integer n (1 ≤ n ≤ 200000).
Output a single integer – the number circular strings of length n.