He`s Circles

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.

Input

The input file contains a single integer n (1 ≤ n ≤ 200000).

Output

Output a single integer – the number circular strings of length n.

Examples