Colorful Tree Coloring

A teacher at the Zhichuan Institute gave Xiao Zhi a task. The teacher provided a piece of paper with a tree having \(n\) nodes (if you are not familiar with the tree data structure, please refer to the previous problem for a detailed explanation) and \(m\) pens, each with a distinct color. Xiao Zhi is asked to color every node of the tree with one of these \(m\) colors so that:

1. Every node is painted in exactly one of the \(m\) colors.
2. Any two nodes connected by an edge (i.e. adjacent nodes) must have different colors.
3. For every color, the number of nodes painted with that color does not exceed \(\left\lfloor\frac{n}{3}\right\rfloor+1\).

Note that even though every node must receive a color, it is not necessary to use all \(m\) colors. Xiao Zhi, finding this task too simple, wonders: how many valid colorings are there that satisfy these conditions? Since the answer may be very large, output the result modulo \(998\,244\,353\).

Two colorings are considered different if there exists at least one node whose color differs between the two colorings.

inputFormat

The first line of input contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq \text{small})\), representing the number of nodes and the number of available colors, respectively. The following \(n-1\) lines each contain two integers \(u\) and \(v\) (1-indexed) indicating that there is an edge between node \(u\) and node \(v\), which together form a tree.

outputFormat

Output a single integer — the number of valid colorings of the tree under the constraints, taken modulo \(998\,244\,353\).

sample

3 3
1 2
2 3

12