For a tree $T(V, E)$ and $S \subseteq V$, let $f(S, T)$ denote the number of vertices with degree at most 1 in the subgraph of $T$ induced by $S$ (i.e., the graph obtained by keeping only the vertices in $S$ and the edges whose both endpoints are in $S$).

For two trees $T_1(V_1, E_1)$ and $T_2(V_2, E_2)$, if $V_1 = V_2$, we say $T_1 \preccurlyeq T_2$ if and only if for any $S_2 \subseteq V_2$, there exists $S_1$ such that $S_2 \subseteq S_1 \subseteq V_1$ and $f(S_1, T_1) \leq f(S_2, T_2)$.

We say $T_1, T_2$ are equivalent if $T_1 \preccurlyeq T_2$ and $T_2 \preccurlyeq T_1$, denoted as $T_1 \sim T_2$. This equivalence relation partitions the labeled trees with $n$ vertices into several equivalence classes.

Questions: 1. Given $k$ trees $T_1, T_2, \dots, T_k$ with $n$ vertices, find the number of equivalence classes of labeled trees $T$ such that $T \preccurlyeq T_i$ for all $1 \leq i \leq k$. 2. Given $k$ trees $T_1, T_2, \dots, T_k$ with $n$ vertices, find the number of labeled trees $T$ such that $T_i \preccurlyeq T$ for all $1 \leq i \leq k$.

Note that the objects being counted in the two questions are different. Both answers should be taken modulo $998,244,353$. It is guaranteed that the answers are non-zero after modulo.

Input

Read data from standard input. The first line contains an integer $p$, where $p \in \{0, 1\}$. $p=0$ indicates the first question, and $p=1$ indicates the second question. The next line contains two positive integers $k$ and $n$, representing the number of trees and the number of vertices, respectively. Then, $k$ trees are given. For each tree, $n-1$ lines follow, each containing two positive integers $u, v$ describing an edge in the tree.

Output

Output to standard output. Output a single integer representing the result modulo $998,244,353$.

Examples

Input 1

0
1 4
1 2
1 3
1 4

Output 1

2

Note

It can be proven that the labeled trees with 4 vertices are partitioned into 5 equivalence classes. All paths are in the same equivalence class, while others correspond to equivalence classes where each vertex acts as the center of a star graph. It can be verified that the equivalence class corresponding to the path and the equivalence class containing the tree itself satisfy the requirements, while other equivalence classes do not.

Input 2

1
1 4
1 2
2 3
3 4

Output 2

16

Note

It can be verified that all 16 labeled trees with 4 vertices satisfy the requirements.

Examples 3-10

See the files 3.in and 3.ans through 10.in and 10.ans in the problem directory.

Subtasks

For all data, it is guaranteed that $p \in \{0, 1\}$, $3 \leq n \leq 5000$, $1 \leq k \leq 1000$, $1 \leq u, v \leq n$, and the answer is non-zero after modulo.

In "Tree Shape", "Star" refers to a tree where there exists a vertex directly connected to all other vertices, and "Path" refers to a tree where all vertices have a degree of at most 2.