{"raw_statement":[{"iden":"problem statement","content":"You are given positive integers $N$ and $K$. Consider an undirected tree $T$ with $(2K + 1)N + 1$ vertices labeled from $1$ to $(2K + 1)N + 1$. Among all such trees, find the number, modulo $998244353$, of trees that satisfy the following condition.\n\n*   It is possible to remove all edges from $T$ by repeating the following operation:\n    *   Choose a path of length $2K + 1$ and remove all edges in it.  \n        Formally, choose a sequence of distinct vertices $v_0, v_1, \\dots, v_{2K+1}$ such that there exists an edge $(v_i, v_{i+1})$ for all $i$ such that $0 \\leq i \\leq 2K$, and remove the edge $(v_i, v_{i+1})$ for all $i$ such that $0 \\leq i \\leq 2K$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 1.3 \\times 10^5$\n*   $1 \\leq K \\leq 50$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$"},{"iden":"sample input 1","content":"2 1"},{"iden":"sample output 1","content":"8820\n\nFor example, consider a tree with edges $(1, 2)$, $(2, 3)$, $(2, 4)$, $(2, 6)$, $(3, 7)$, and $(4, 5)$. By doing the following steps, one can remove all edges from the tree, so it satisfies the condition in the problem statement:\n\n*   Choose the path $(1,2,4,5)$ and remove edges $(1,2)$, $(2,4)$, $(4,5)$.\n*   Choose the path $(6,2,3,7)$ and remove edges $(6,2)$, $(2,3)$, $(3,7)$.\n\n![image](https://img.atcoder.jp/agc070/97f1043f2e834a849e1e3d10921cfb9b.png)\nThere are $8820$ such trees in total."},{"iden":"sample input 2","content":"70 1"},{"iden":"sample output 2","content":"273892456\n\nRemember to print the count modulo $998244353$."},{"iden":"sample input 3","content":"12 29"},{"iden":"sample output 3","content":"898069699"},{"iden":"sample input 4","content":"100000 50"},{"iden":"sample output 4","content":"158600909"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}