He's Circles#7125

He's Circles

2.5 seconds

64 megabytes

Very easy

Vasya wrote $n$ letters "X" and "E" in a circle. He thought that there were $2^{n}$ 2^n possibilities to do it, because each letter may be either "X" or "E". However, Petya noticed that some different sequences of letters can be transformed into each other by a circular shift (thus representing the same circular string).

For example, the strings "XXE", "XEX", and "EXX" are actually the same.

Petya wants to know how many different circular strings of $n$ letters exist. Help him find that out.

Input

The input consists of a single integer $n$ ( $1 \leq n \leq 200000$ 1 \leq n \leq 200000).

Output

Output a single integer: the number of distinct circular strings of length $n$ .

Examples

Example 1

Loading

2^{n}

1 \leq n \leq 200000