{"raw_statement":[{"iden":"problem statement","content":"For a positive integer $N$, a rooted binary tree that satisfies the following conditions is said to be a **beautiful binary tree of degree $N$**.\n\n*   Each vertex has $0$ or $1$ written on it.\n*   Each vertex that is a leaf has $1$ written on it.\n*   It is possible to do the following operation at most $N-1$ times so that the root has $N$ written on it and the other vertices have $0$ written on them.\n    *   Choose vertices $u$ and $v$, where $v$ must be a child of $u$ or a child of \"a child of $u$.\" Let $a_u \\gets a_u + a_v, a_v \\gets 0$, where $a_u$ and $a_v$ are the numbers written on $u$ and $v$, respectively.\n\nGiven $N$, find the number, modulo $998244353$, of beautiful binary trees of degree $N$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^7$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$"},{"iden":"sample input 1","content":"1"},{"iden":"sample output 1","content":"1\n\nThe only binary tree that satisfies the condition is a tree with one vertex whose root has $1$ written on it."},{"iden":"sample input 2","content":"2"},{"iden":"sample output 2","content":"6\n\nThe binary trees that satisfy the condition are the six trees shown below.\n![image](https://img.atcoder.jp/ghi/37c6125e227d459cd725b6ccec96e2c8.png)"},{"iden":"sample input 3","content":"222"},{"iden":"sample output 3","content":"987355927"},{"iden":"sample input 4","content":"222222"},{"iden":"sample output 4","content":"675337738"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}