Counting Trees with Maximum Degree Constraint

DLS loves climbing trees, but he doesn’t want to stick with a typical data structure tree; he loves counting trees. Today, he decides to build his own tree using N nodes numbered from 1 to N. He will add edges between them so that they form a tree. Two trees are considered different if and only if there is a pair of nodes that are adjacent in one tree but not in the other.

However, DLS does not like trees with too many branches. Therefore, he requires that the maximum degree among all nodes is exactly M.

You are to compute the number of such trees modulo 998244353.

Recall that a tree on N nodes has exactly N-1 edges, and by the Prüfer code correspondence, each tree can be represented as a sequence of length \(N-2\) where the degree of each vertex \(i\) is \(\text{count}(i)+1\). Hence, the condition that the maximum degree is exactly \(M\) is equivalent to requiring that for each vertex, its frequency in the Prüfer code is at most \(M-1\), with at least one vertex attaining exactly \(M-1\) occurrences.

The answer is the number of trees with maximum degree at most \(M\) minus the number of trees with maximum degree at most \(M-1\). More formally, if we let \(F(D)\) denote the number of Prüfer sequences of length \(N-2\) in which each vertex appears at most \(D-1\) times, then the desired answer is

[ \text{Answer} = F(M) - F(M-1) \pmod{998244353}. ]

You may assume that \(N \ge 1\) and \(M \ge 1\). (Note that for \(N \ge 3\) the tree always has a vertex of degree at least 2.)

inputFormat

The input consists of a single line containing two integers N and M separated by a space.

outputFormat

Output a single integer — the number of trees on N nodes whose maximum degree is exactly M, taken modulo 998244353.

sample

2 1

1