题目背景

ZYG解出了谜题并输入密码，发现锁并没有开，并且门发出了嘲讽的声音。
ZYG非常气愤，一个滑铲踹开了门，终于离开雾雨魔法店。但因为魔法森林的瘴气太重，他没走几步就晕倒在地，醒来时发现周围有一只九尾狐和一只二尾化猫，化猫邀请他玩一个玩具。

题目描述

这个玩具有\(n\)层钉子，第\(i\)层有\(i\)个钉子，如右上图所分布：
把小球从最上方的钉子处正上方自由下落，小球每次碰到一根钉子后会飞向下一层的距离它最近的两个钉子中的一个，飞到两个钉子中某一个钉子的概率都是\(50\%\)。第\(n+1\)层有\(n+1\)个槽，小球与\(n\)个钉子碰撞完后落入一个槽内，该槽为距离球所碰撞的第\(n\)个钉子最近的两个中的一个，且钉子落入两个槽中的某一个的概率都是\(50\%\)。

ZYG 突然考虑到一个问题。如右下图所示，对于每个槽，从左到右数第\(i\)个槽下有一个数字\(C_{N}^{i-1}\)。现在在最上方的钉子的正上方使一小球自由下落，则小球所落入槽的正下方的数字的数学期望是多少？

Format

输入格式

共一行，一个正整数\(n\)，如题所述。

输出格式

共一行，即为ZYG所想知道的答案，若答案为分数\(p/q\)（\(p\)与\(q\)皆为整数），
则请输出\(p \cdot q^{-1}\)对\(19260817\)取模的结果（\(q^{-1}\)为\(q\)在模\(19260817\)下的逆元）。

Sample 1

Input

3 

Output

9630411

Limitation

1s, 512MiB for each test case.

Hint

① 对于30%的数据，\(n \leq 10\)；对于100%的数据，\(n \leq 100000\)。
② \(n=3\)时是答案为\(5/2\)，\(5/2 \equiv 9630411(mod 19260817)\)。

Source

8月23日 炎炎夏日大礼包