{"problem":{"name":"BFS-ordered Tree","description":{"content":"You are given an integer $N$. We call a rooted tree $T$ satisfying the following conditions a **BFS-ordered tree**. *   $T$ is a rooted tree with $N$ vertices numbered from $1$ to $N$. *   The root i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"awtf2025_d"},"statements":[{"statement_type":"Markdown","content":"You are given an integer $N$. We call a rooted tree $T$ satisfying the following conditions a **BFS-ordered tree**.\n\n*   $T$ is a rooted tree with $N$ vertices numbered from $1$ to $N$.\n*   The root is vertex $1$.\n*   Let vertex $p_i$ be the parent of each vertex $i$ ($2 \\leq i \\leq N$). Then, $p_2 \\leq p_3 \\leq \\cdots \\leq p_N$ holds.\n\nFor each $d=1,2,\\ldots,(N-1)$, find the number, modulo $998244353$, of BFS-ordered trees $T$ satisfying the following condition.\n\n*   The distance between vertices $(N-1)$ and $N$ in $T$ is exactly $d$. More precisely, when considering $T$ as an undirected tree and the path connecting vertices $(N-1)$ and $N$, the number of edges in that path is exactly $d$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^6$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"awtf2025_d","tags":[],"sample_group":[["2","1"],["3","1\n1"],["4","2\n2\n1"],["5","5\n5\n3\n1"],["20","477638700\n477638700\n178405156\n178405139\n109639972\n108787985\n86366256\n69212603\n43976909\n22930595\n9698374\n3355343\n947052\n215710\n38814\n5324\n524\n33\n1"]],"created_at":"2026-03-03 11:01:13"}}