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