Вася выписал n букв "X" и "E" по кругу. Вася подумал, что получится 2^n вариантов сделать это, так как каждая буква может быть либо "X", либо "E". Однако Петя заметил, что некоторые различные последовательности букв могут быть преобразованы друг в друга циклическим сдвигом (таким образом представляя одну и ту же циклическую строку).
Например, строки "XXE"-"XEX"-"EXX" на самом деле одинаковы.
Петя хочет знать, сколько существует различных циклических строк из n букв. Помогите ему это узнать.
Одно число n (1 ≤ n ≤ 200000).
Вывести количество циклических строк длины n.