背景

^_^

题目描述

现在有一个解谜游戏。这个解谜游戏的地图上一共有 N 个房间，形成了一棵 N 个点的有根二叉树，而在二叉树的每个叶子节点上都有一条解谜的线索。

现在想知道对于所有可能出现的包含 N 个房间的地图中，解谜线索的期望条数（每种可能出现的地图等概率出现）。

可以证明，线索的期望条数一定是一个有理数 $\frac{p}{q}$，你只需要输出这个数在模 2148473647 意义下的余数即可。

如果你没有学过如何对一个分数进行取模，你可以认为本题要你输出的是 $p⋅q^{mod−2}$（其中 mod=2148473647） 在模 2148473647 意义下的余数。

格式

输入

一行一个整数 N$(1≤N≤10^9)$。

输出

一行一个整数 X(0≤X<2148473647)，表示要你输出的答案。

样例

3

859389460

样例解释

一共有 5 种可能的地图，4 种只有 1 条线索，1 种有 2 条线索，线索的期望条数为 $\frac{6}{5}$ 。

测试限制

对于20%的数据，n≤20;

对于40%的数据，n≤2000;

对于70%的数据，$n≤10^6$;

对于100%的数据，$n≤10^9$。

每个测试点均为 1s, 1024KiB .