Cycles in product

给你大小为$n_1$和$n_2$的两棵树$T_1$和$T_2$，构造一张新图，该图中每一个点的编号为$(u,v)$。如果在$T_1$中，$u_1$和$u_2$之间有边，那么在该图上，对于任意$v$，$(u_1,v)$和$(u_2,v)$之间有边。同样，如果在$T_2$中，$v_1$和$v_2$之间有边，那么在图上，$(u,v_1)$和$(u,v_2)$之间有边。 问你这个图上长度为$K$的环有多少个，定义环为从一个点出发，走$K$步回到起点，可以经过重复点和重复边。 $n_1,n_2 \leq 4000,k \leq 75$，答案对998244353取模

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.

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.

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

2 2 2
1 2
1 2

8

2 2 4
1 2
1 2

32

2 3 4
1 2
1 2
1 3

70

4 2 2
1 2
1 3
1 4
1 2

20

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»