{"problem":{"name":"Overlap Binary Tree","description":{"content":"You are given an **odd** number $N$ and a non-negative integer $K$. Find the number, modulo $998244353$, of sequences of integer pairs $((L_1,R_1),(L_2,R_2),\\dots,(L_N,R_N))$ satisfying all of the fol","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc062_e"},"statements":[{"statement_type":"Markdown","content":"You are given an **odd** number $N$ and a non-negative integer $K$.\nFind the number, modulo $998244353$, of sequences of integer pairs $((L_1,R_1),(L_2,R_2),\\dots,(L_N,R_N))$ satisfying all of the following conditions.\n\n*   $(L_1,R_1,L_2,R_2,\\dots,L_N,R_N)$ is a permutation of the integers from $1$ to $2N$.\n*   $L_1 \\leq L_2 \\leq \\dots \\leq L_N$.\n*   $L_i \\leq R_i \\ (1 \\leq i \\leq N)$.\n*   There are exactly $K$ indices $i\\ (1\\leq i \\leq N)$ such that $L_i+1=R_i$.\n*   There is a rooted binary tree $T$ with $N$ vertices numbered from $1$ to $N$ such that the following holds:\n    *   vertices $i$ and $j$ have an ancestor-descendant relationship in $T$ $\\iff$ intervals $[L_i,R_i]$ and $[L_j,R_j]$ intersect.\n\nHere, a rooted binary tree is a rooted tree where each vertex has $0$ or $2$ children. Vertices $i$ and $j$ are said to have an ancestor-descendant relationship in a tree $T$ if either vertex $j$ exists on the simple path connecting the root to vertex $i$, or vice versa.\n\n## Constraints\n\n*   $1 \\leq N < 2 \\times 10^5$\n*   $0 \\leq K \\leq N$\n*   $N$ is odd.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc062_e","tags":[],"sample_group":[["3 1","2\n\nFor example, if $(L_1,R_1)=(1,5),(L_2,R_2)=(2,3),(L_3,R_3)=(4,6)$, then $i=2$ is the only pair with $L_i+1=R_i$. Also, the fifth condition is satisfied by a tree where vertex $1$ is the root, and its children are vertices $2$ and $3$."],["1 0","0"],["521 400","0"],["199999 2023","283903125"]],"created_at":"2026-03-03 11:01:14"}}