{"problem":{"name":"Beautiful Binary Tree","description":{"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$**. *   Each vertex has $0$ or $1$ written on it. *   Eac","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc222_h"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^7$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc222_h","tags":[],"sample_group":[["1","1\n\nThe only binary tree that satisfies the condition is a tree with one vertex whose root has $1$ written on it."],["2","6\n\nThe binary trees that satisfy the condition are the six trees shown below.\n![image](https://img.atcoder.jp/ghi/37c6125e227d459cd725b6ccec96e2c8.png)"],["222","987355927"],["222222","675337738"]],"created_at":"2026-03-03 11:01:13"}}