CF997D.Cycles in product

Consider a tree (that is, an undirected connected graph without loops) $T_1$ and a tree $T_2$. Let's define their cartesian product $T_1 \times T_2$ in a following way.

Let $V$ be the set of vertices in $T_1$ and $U$ be the set of vertices in $T_2$.

Then the set of vertices of graph $T_1 \times T_2$ is $V \times U$, that is, a set of ordered pairs of vertices, where the first vertex in pair is from $V$ and the second — from $U$.

Let's draw the following edges:

• Between $(v, u_1)$ and $(v, u_2)$ there is an undirected edge, if $u_1$ and $u_2$ are adjacent in $U$.
• Similarly, between $(v_1, u)$ and $(v_2, u)$ there is an undirected edge, if $v_1$ and $v_2$ are adjacent in $V$.

Please see the notes section for the pictures of products of trees in the sample tests.

Let's examine the graph $T_1 \times T_2$. How much cycles (not necessarily simple) of length $k$ it contains? Since this number can be very large, print it modulo $998244353$.

The sequence of vertices $w_1$, $w_2$, ..., $w_k$, where $w_i \in V \times U$ called cycle, if any neighboring vertices are adjacent and $w_1$ is adjacent to $w_k$. Cycles that differ only by the cyclic shift or direction of traversal are still considered different.

考虑两棵树（即无环的无向连通图）$T_1$ 与 $T_2$。我们如下定义它们的笛卡尔积 $T_1 \times T_2$。

设 $V$ 为 $T_1$ 的顶点集，$U$ 为 $T_2$ 的顶点集。

则图 $T_1 \times T_2$ 的顶点集为 $V \times U$，即所有有序顶点对构成的集合，其中每对的第一个顶点属于 $V$，第二个顶点属于 $U$。

我们添加如下边：

• 若 $u_1$ 与 $u_2$ 在 $U$ 中相邻，则在 $(v, u_1)$ 与 $(v, u_2)$ 之间连一条无向边；
• 类似地，若 $v_1$ 与 $v_2$ 在 $V$ 中相邻，则在 $(v_1, u)$ 与 $(v_2, u)$ 之间连一条无向边。

有关样例测试中树的笛卡尔积的示意图，请参见“注释”部分。

现在考察图 $T_1 \times T_2$：它包含多少条长度为 $k$ 的环（不一定是简单环）？由于该数目可能非常大，请输出其对 $998244353$ 取模的结果。

顶点序列 $w_1, w_2, \dots, w_k$（其中每个 $w_i \in V \times U$）称为一个环，当且仅当任意两个相邻顶点均邻接，且 $w_1$ 与 $w_k$ 邻接。仅因循环移位或遍历方向不同而产生的环仍被视为不同的环。

First line of input contains three integers — $n_1$, $n_2$ and $k$ ($2 \le n_1, n_2 \le 4000$, $2 \le k \le 75$) — number of vertices in the first tree, number of vertices in the second tree and the cycle length respectively.

Then follow $n_1 - 1$ lines describing the first tree. Each of this lines contains two integers — $v_i, u_i$ ($1 \le v_i, u_i \le n_1$), which define edges of the first tree.

Then follow $n_2 - 1$ lines, which describe the second tree in the same format.

It is guaranteed, that given graphs are trees.

输入的第一行包含三个整数 — $n_1$、$n_2$ 和 $k$（$2 \le n_1, n_2 \le 4000$，$2 \le k \le 75$），分别表示第一棵树的顶点数、第二棵树的顶点数以及环的长度。

接下来是 $n_1 - 1$ 行，用于描述第一棵树。每行包含两个整数 $v_i$、$u_i$（$1 \le v_i, u_i \le n_1$），表示第一棵树的一条边。

随后是 $n_2 - 1$ 行，以相同格式描述第二棵树。

保证所给图均为树。

Print one integer — number of cycles modulo $998244353$.

输出一个整数——环的数量对 $998244353$ 取模的结果。

The following three pictures illustrate graph, which are products of the trees from sample tests.

In the first example, the list of cycles of length $2$ is as follows:

• «AB», «BA»
• «BC», «CB»
• «AD», «DA»
• «CD», «DC»

以下三张图片展示了图结构，它们分别是样例测试中树的乘积。

在第一个例子中，长度为 $2$ 的环的列表如下：

• «AB»、«BA»
• «BC»、«CB»
• «AD»、«DA»
• «CD»、«DC»