eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Васин круг

Васин круг

Ліміт часу 2.5 секунди
Ліміт використання пам'яті 64 MiB

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

Наприклад, рядки "XXE"-"XEX"-"EXX" насправді однакові.

Петя хоче знати, скільки існує різних циклічних рядків з n букв. Допоможіть йому це взнати.

Вхідні дані

Одне число n (1n200000).

Вихідні дані

Вивести кількість циклічних рядків довжини n.

Приклад

Вхідні дані #1
3
Вихідні дані #1
4
Автор Антон Голубев
Джерело 2005 Літні тренувальні сбори у Петрозаводську, Контест #2 Антона Голубєва, Серпень 26, Задача H