序列变换

题目描述

给定一个正整数 $n$ 和长度为 $2^n$ 的序列，序列中的元素初始依次为 $1,2,3,...,2^n$.

现在将进行 $k$ 次操作，每次操作会通过当前序列 $A$ 得到更新序列 $B$，具体地：

1.将 $A$ 序列第 $1,3,5,...,2^n-1$ 个元素取出，依次组成 $B$ 序列的第 $1,2,3,...,2^{n-1}$ 个元素。

2.将 $A$ 序列第 $2,4,6,...,2^n$ 个元素取出，依次组成 $B$ 序列的第 $2^{n-1}+1,2^{n-2}+2,2^{n-1}+3,...,2^n$ 个元素。

例如：$n=3$ 时,每次操作后的序列如下标：

注意到在进行若干次操作后，部分元素又回到了原来的位置。

记 $C(x)$ 表示元素 $x$ 第一次回到位置 $x$ 的操作次数。如 $C(1)=1,C(3)=3$.

现在请你回答，对于所有 $1$ 到 $2^n$ 中的整数 $x$,有多少种不同的 $C(x)$.

输入格式

一行输入一个正整数 $n$.

输出格式

一行输出一个整数，表示不同的 $C(x)$ 种数。

输入输出样例 #1

输入 #1

3

输出 #1

2

输入输出样例 #2

输入 #2

10

输出 #2

4

输入输出样例 #3

输入 #3

493920

输出 #3

144

说明/提示

【数据范围】

对于所有数据，保证 $1 \le n \le 10^{12}$.