Васин круг

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

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

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

Вхідні дані

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

Вихідні дані

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

Приклади