There are $$$n$$$ cities in Byteland connected by $$$n-1$$$ bidirectional roads, forming a tree, i.e., for any two cities, there is exactly one simple path between them.
Colin, the leader of Byteland, plans to establish the broadcasting system by establishing communication stations in some cities, with at most one station per city. For any two stations, if there is no other station on the path between them, they must develop a direct connection. The cost of such a connection equals the number of roads between them, i.e., their distance in the tree.
For a construction plan $$$S$$$ (a subset of cities with stations), define:
The allocated budget for plan $$$S$$$ is $$$budget(S) = |S| \times val(S).$$$
Colin wants to compute the sum of budgets over all possible $$$2^n$$$ construction plans. Two plans are different if and only if there exists at least one city where the presence of a station differs.
Since the answer can be large, output it modulo $$$998244353$$$.
The first line contains a single integer $$$n~(2\leq n\leq 10^6)$$$, representing the number of cities.
For the following $$$n-1$$$ lines, each line contains two positive integers $$$u, v~(1\leq u, v\leq n,u\ne v)$$$ representing a road in Byteland. It is guaranteed that all the roads connect $$$n$$$ cities into a tree.
Output a single integer, representing the answer.
31 21 3
14
41 21 31 4
66
For the first example,
When there are fewer than two stations, the budget needed is $$$0$$$;
When the stations are built at $$$\{1,2\}$$$ or $$$\{1,3\}$$$, the budget needed is $$$2$$$;
When the stations are built at $$$\{2,3\}$$$, the budget needed is $$$4$$$;
When the stations are built at $$$\{1,2,3\}$$$, the budget needed is $$$6$$$.
