对于树 $T(V,E)$ 和 $S\subseteq V$，记 $f(S,T)$ 表示 $T$ 的对 $S$ 的导出子图（即仅保留 $S$ 中的点和两端都在 $S$ 中的边得到的图）中度数小于等于 $1$ 的点的数量。

对于两棵树 $T_1(V_1,E_1),T_2(V_2,E_2)$，若 $V_1=V_2$，我们称 $T_1\preccurlyeq T_2$ 当且仅当对于任意 $S_2\subseteq V_2$，存在 $S_1$ 满足 $S_2\subseteq S_1\subseteq V_1$ 且 $f(S_1,T_1)\le f(S_2,T_2)$。

称 $T_1,T_2$ 等价当 $T_1\preccurlyeq T_2$ 且 $T_2\preccurlyeq T_1$，记作 $T_1\sim T_2$。该等价关系将 $n$ 个点的有标号树划分成若干等价类。

问：

1. 给定 $k$ 棵 $n$ 个点的树 $T_1,T_2\dots ,T_k$，求满足 $T\preccurlyeq T_i,\forall 1\le i\le k$ 的有标号树 $T$ 构成的等价类数量。

2. 给定 $k$ 棵 $n$ 个点的树 $T_1,T_2\dots ,T_k$，求满足 $T_i\preccurlyeq T,\forall 1\le i\le k$ 的有标号树 $T$ 数量。

注意两问的计数对象不同。两问答案均对 $998,244,353$ 取模。

保证答案取模后非 $0$。

输入格式

从标准输入读入数据。

输入第一行一个整数 $p$，其中 $p\in \{0,1\}$，$p=0$ 表示询问第一问，否则表示询问第二问。

接下来一行两个正整数 $k,n$，分别表示输入树的数量以及点数。

接下来依次输入 $k$ 棵树，对于每棵树输入 $n-1$ 行每行两个正整数 $u,v$ 描述树中的一条边。

输出格式

输出到标准输出。

输出一行一个整数表示答案对 $998,244,353$ 取模后的结果。

样例 1

input

0
1 4
1 2
1 3
1 4

output

2

explanation

可以证明 $4$ 个点的有标号树被划分成了 $5$ 个等价类，所有的链在同一个等价类，而其它分别以每个点为菊花中心对应一个等价类。

可以验证链对应的等价类和该树本身所在的等价类均满足要求，而其他等价类不满足要求。

样例 2

input

1
1 4
1 2
2 3
3 4

output

16

explanation

可以验证所有 $4$ 个点的有标号树共 $16$ 个均满足要求。

样例 3 ~ 10

见题目目录下的 3.in ~ 10.in 与 3.ans ~ 10.ans。

子任务

对于所有数据，保证 $p\in \{0,1\}$，$3\le n\le 5000$，$1\le k\le 1000$，$1\le u,v\le n$，答案取模后不等于 $0$。

“树形态”中，“菊花”指存在一个向所有点有直接连边的点，“链”指所有点度数不超过 $2$。