假设有 $n$ 名选手参加一场单败淘汰赛。比赛按轮次进行。设 $k$ 为该轮开始时剩余的选手人数。他们将随机组成 $\lfloor \frac{k}{2} \rfloor$ 对选手。任何一种可能的配对方式被选中的概率均相等。在每一对中，两名选手进行比赛，其中一人获胜，负者被淘汰。剩下的 $\lceil \frac{k+1}{2} \rceil$ 名选手晋级下一轮。

已知每位参赛者都有唯一的等级分，且每场比赛的结果完全由等级分决定：等级分较高者获胜。因此，唯一影响比赛进程的因素是每一轮中随机的配对方式。你能计算出可能发生的比赛情况总数吗？如果两场比赛中存在一场比赛（即两名选手之间的对局）在另一场比赛中未出现，则称这两场比赛是不同的。由于答案可能非常大，请计算该数值对 $2^{64}$ 取模的结果。

输入格式

输入包含一个整数 $n$：锦标赛的初始选手人数 ($1 \le n \le 10^{18}$)。

输出格式

输出不同比赛情况的数量，对 $2^{64}$ 取模。

样例

样例输入 1

4

样例输出 1

3

样例输入 2

5

样例输出 2

45