解谜
现在有⼀个解谜游戏。这个解谜游戏的地图上⼀共有$n$个房间，形成了⼀棵 个点的有根⼆叉树，⽽
在⼆叉树的每个叶⼦节点上都有⼀条解谜的线索。
现在想知道对于所有可能出现的包含$n$个房间的地图中，解谜线索的期望条数（每种可能出现的地图
等概率出现）。
可以证明，线索的期望条数⼀定是⼀个有理数 ，你只需要输出这个数在模$mod$意义下的余
数即可。
如果你没有学过如何对⼀个分数进⾏取模，你可以认为本题要你输出的是 p*q^(mod-2)（其中mod=INT_MAX
） 在模$mod$意义下的余数。
输⼊格式
⼀⾏⼀个整数 $n(1<=n<=1e9)$。
输出格式
⼀⾏⼀个整数 ，表示要你输出的答案。
样例
输⼊
3
输出
859389460
样例解释
⼀共有 种可能的地图， 种只有 条线索， 种有 条线索，线索的期望条数为 。
数据范围
对于20%的数据， $n<=20$;
对于40%的数据， $n<=2000$;
对于70%的数据， $n<=1e6$;
对于100%的数据，$n<=1e18$ 。
时间限制 $1s$
空间限制 $512M$