Васин круг

Вася выписал n букв "X" и "E" по кругу. Вася подумал, что получится 2^n вариантов сделать это, так как каждая буква может быть либо "X", либо "E". Однако Петя заметил, что некоторые различные последовательности букв могут быть преобразованы друг в друга циклическим сдвигом (таким образом представляя одну и ту же циклическую строку).

Например, строки "XXE"-"XEX"-"EXX" на самом деле одинаковы.

Петя хочет знать, сколько существует различных циклических строк из n букв. Помогите ему это узнать.

Входные данные

Одно число n (1 ≤ n ≤ 200000).

Выходные данные

Вывести количество циклических строк длины n.

Примеры