Little $\sigma$ has a social network containing $n$ people and $n-1$ friendship relations. It is guaranteed that everyone is connected in this network; that is, if we view the $n$ people as vertices and the $n-1$ friendship relations as edges, then the network is a tree.

The network can change—after all, there are no friends forever.

Little $\sigma$ often reminisces about the past. He thinks that the network in the past is the reconstruction tree obtained from the current network by adding vertices in the order $1,2,3,\dots,n$.

Little $\sigma$ often fantasizes about the future. He finds that the network in the future is the reconstruction tree obtained from the current network by adding vertices in the order $n,n-1,n-2,\dots,1$.

Little $\sigma$ defines: given two networks, if a non-empty subset $S$ of ${1,2,3,\dots,n}$ induces a subgraph that is a single connected component in both networks, then $S$ is an invariant friend subset of these two networks.

Little $\sigma$ wants to know:

• how many invariant friend subsets there are between the past network and the current network, and
• how many invariant friend subsets there are between the past network and the future network.

Since the answer may be large, you only need to output it modulo $998244353$.

Formal Statement

Given a tree $T$ with $n$ vertices, define:

• $T_{\max}$ as the reconstruction tree obtained by adding vertices in the order $1,2,3,\dots,n$,
• $T_{\min}$ as the reconstruction tree obtained by adding vertices in the order $n,n-1,n-2,\dots,1$,
• $f(T_1,T_2)$ as the number of non-empty subsets $S \subseteq {1,2,3,\dots,n}$ such that the subgraph induced by $S$ is a connected component in both $T_1$ and $T_2$.

Compute $f(T_{\max},T)$ and $f(T_{\max},T_{\min})$ modulo $998244353$.

The specific procedure to build a reconstruction tree by adding vertices in the order $ord_1,ord_2,ord_3,\dots,ord_n$ is:

1. Maintain a vertex set $S$, and traverse $i=1,2,3,\dots,n$ in order, letting $p=ord_i$.
2. For every vertex $q$ that is adjacent to $p$ in the original tree and is already in $S$, connect $p$ (in the reconstruction tree) to the vertex that was added last to $S$ within the connected component containing $q$ in the subgraph induced by $S$.
3. Add $p$ to the set $S$.

Input Format

The first line contains two positive integers $tp,n$, representing the query type and the number of vertices.

• If $tp=1$, you need to output how many invariant friend subsets exist between the past network and the current network.
• If $tp=2$, you need to output how many invariant friend subsets exist between the past network and the future network.

The next $n-1$ lines each contain two positive integers $u_i,v_i$, describing a friendship relation (an edge). It is guaranteed that the network is connected.

Output Format

Output one line containing a non-negative integer: the answer modulo $998244353$.

Example

Example 1 Input

1 6
3 1
1 6
6 4
4 2
4 5

Example 1 Output

15

Example 2 Input

2 6
3 1
1 6
6 4
4 2
4 5

Example 2 Output

13

Constraints

For all data: $1\leq tp\leq 2$, $1\leq n\leq 2\times 10^5$, and the network is guaranteed to be connected.