곱에서의 사이클

트리(즉, 루프가 없는 무방향 연결 그래프) $T_1$와 트리 $T_2$를 생각해 보자. 이들의 데카르트 곱 $T_1$ × $T_2$를 다음과 같이 정의한다.

Let V를 $T_1$의 정점 집합이라 하고, U를 $T_2$의 정점 집합이라 하자.

그러면 그래프 $T_1$ × $T_2$의 정점 집합은 V × 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$ × $T_2$를 살펴보자. 이 그래프에는 길이가 k인 사이클(단순 사이클일 필요는 없음)이 몇 개 있는가? 이 수는 매우 클 수 있으므로 998244353으로 나눈 나머지를 출력한다.

정점들의 수열 $w_1$, $w_2$, ..., $w_k$에서 $w_i$ ∈ V × U일 때, 연속한 모든 정점이 인접하고 $w_1$이 $w_k$와 인접해 있다면 이 수열을 사이클이라고 한다. 순환 이동이나 순회 방향만 다른 사이클도 서로 다른 것으로 간주한다.

입력의 첫 번째 줄에는 세 정수 $n_1$, $n_2$, k (2 ≤ $n_1$, $n_2$ ≤ 4000, 2 ≤ k ≤ 75)가 주어진다. 각각 첫 번째 트리의 정점 수, 두 번째 트리의 정점 수, 사이클의 길이이다.

이어서 첫 번째 트리를 설명하는 $n_1$ - 1개의 줄이 주어진다. 각 줄에는 첫 번째 트리의 간선을 정의하는 두 정수 $v_i$, $u_i$ (1 ≤ $v_i$, $u_i$ ≤ $n_1$)가 주어진다.

이어서 같은 형식으로 두 번째 트리를 설명하는 $n_2$ - 1개의 줄이 주어진다.

주어진 그래프들이 트리임이 보장된다.

사이클의 수를 998244353으로 나눈 나머지인 정수 하나를 출력한다.

다음 세 그림은 예제 테스트에 등장하는 트리들의 곱인 그래프를 보여 준다.

첫 번째 예제에서 길이가 2인 사이클의 목록은 다음과 같다:

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