Васине коло#7125
Вася записав букв "X" і "E" по колу. Він подумав, що існує 2^n способів це зробити, оскільки кожна буква може бути або "X", або "E". Однак Петро зауважив, що деякі різні послідовності букв можна отримати одну з іншої циклічним зсувом (таким чином вони представляють один і той самий циклічний рядок).
Наприклад, рядки "XXE", "XEX" та "EXX" насправді однакові.
Петро хоче знати, скільки існує різних циклічних рядків з букв. Допоможіть йому це з'ясувати.
Вхідні дані містять одне ціле число (1 \leq n \leq 200000).
Виведіть одне число — кількість різних циклічних рядків довжини .
Приклад 1