问题描述

Qc写了$N$个字母("X"或者"E")，用这些字母组成一个圆环。他以为有$2N$种可能性，因为每个字母可以是"X"或"E"。

但是Qc注意到，一些不同的字母序列可以通过循环移位互相转换（因此实际上代表同一个环形字符串）。

例如，字符串“XXE”、“XEX”和“EXX”实际上是相同的。

Qc想知道用$N$个字母组成的环形字符串有多少种本质不同的方案。请你帮他找出答案。

输入格式

一个整数$N$

输出格式

输出一个整数——长度为$N$的环形字符串的数量。

样例

3

4

4

6

数据范围

$1 \le N \le 2*10^5$

来源

• SGU294
• 信息学奥赛之数学一本通
• stong9070整理