考虑一棵树(即没有循环的无向连通图)$$$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$$$, ..., $$$w_k$$$,其中 $$$w_i \in V \times U$$$ 称为循环,如果任何相邻顶点相邻且 $$$w_1$$$ 与 $$$w_k$$$ 相邻。仅循环移位或遍历方向不同的循环仍然被认为是不同的。
输入
输入的第一行包含三个整数 - $$$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$$$ 行,它们以相同的格式描述第二棵树。
保证给定的图是树。
输出
打印一个整数 — 周期数以 $$$998244353$$$ 为模。
示例
输入 #1
2 2 2 1 2 1 2
输出 #1
8
输入 #2
2 2 4 1 2 1 2
输出 #2
32
输入 #3
2 3 4 1 2 1 2 1 3
输出 #3
70
输入#4
4 2 2 1 2 1 3 1 4 1 2
输出#4
20
注意
下面三张图片说明了图形,它们是样本测试的树木的产物。
在第一个示例中,长度为 $$$2$$$ 的循环列表如下:
- «AB», «BA»
- «BC», «CB»
- «AD», «DA»
- «CD», «DC»