Extreme Pair Contribution

Given a tree (G) with (n) vertices, we define the distance between two vertices (u) and (v) as the number of vertices on the unique simple path between them, denoted by (\operatorname{dis}(u,v)). An unordered pair ((u,v)) (with (u \neq v)) is called an extreme pair if it satisfies [ \forall x \in G, ; \operatorname{dis}(u,x) \le \operatorname{dis}(u,v) \quad \text{and} \quad \operatorname{dis}(v,x) \le \operatorname{dis}(u,v). ] In a tree, it can be shown that the extreme pairs are exactly the pairs ((u,v)) such that (\operatorname{dis}(u,v)) equals the diameter (D) of (G) and both (u) and (v) have eccentricity (D).

For every vertex (x \in G), define its weight (v_x) as the number of extreme pairs whose unique path passes through (x). You are given an integer constant (k) with (k \in {1,2}). Your task is to calculate [ S = \sum_{x \in G} v_x^k \quad (\text{mod } 998244353), ] where the sum is taken over all vertices of the tree.

Note: In the input, the tree is given by (n) and (k) in the first line, followed by (n-1) lines each containing two integers which represent an edge between two vertices. It is guaranteed that the given graph is a tree and the vertices are numbered from 1 to (n).

inputFormat

The first line contains two integers \(n\) and \(k\) where \(n\) is the number of vertices in the tree and \(k\) is either 1 or 2. The next \(n-1\) lines each contain two integers \(u\) and \(v\), representing an edge connecting vertices \(u\) and \(v\).

outputFormat

Output a single integer: the value of \(\sum_{x \in G} v_x^k\) modulo \(998244353\).

sample

2 1
1 2

2