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 × 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 × T_2 is V × 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 × 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 ∈ V × 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.

Input

First line of input contains three integers — n_1, n_2 and k (2 ≤ n_1, n_2 ≤ 4000, 2 ≤ k ≤ 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 ≤ v_i, u_i ≤ 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.

Output

Print one integer — number of cycles modulo 998244353.

Examples

Input

2 2 2
1 2
1 2


Output

8


Input

2 2 4
1 2
1 2


Output

32


Input

2 3 4
1 2
1 2
1 3


Output

70


Input

4 2 2
1 2
1 3
1 4
1 2


Output

20

Note

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» 

<image> <image> <image>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4001, mod = 998244353;
vector<int> g[maxn];
int n, m, k, c[80][80];
int sz[maxn], used[maxn];
int dp1[maxn][80], dp2[maxn][80];
int ANS, ans[80], ans1[80], ans2[80];
void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
void dfs(int v, int p) {
  sz[v] = 1;
  for (auto to : g[v])
    if (!used[to] && to != p) {
      dfs(to, v);
      sz[v] += sz[to];
    }
}
int getctr(int v, int p, int SZ) {
  for (auto to : g[v])
    if (!used[to] && to != p && sz[to] > SZ / 2) return getctr(to, v, SZ);
  return v;
}
void calc_dp(int v, int p, int len, int ban) {
  for (auto to : g[v])
    if (!used[to]) {
      if (to != p) calc_dp(to, v, len, ban);
      if (to != ban) add(dp1[to][len], dp1[v][len - 1]);
      add(dp2[to][len], dp2[v][len - 1]);
    }
}
void calc_ans(int v, int p) {
  for (int i = 0; i <= k; i++)
    for (int j = 0; j + i <= k; j++)
      add(ans[i + j], 1ll * dp1[v][i] * dp2[v][j] % mod);
  for (auto to : g[v])
    if (!used[to] && to != p) calc_ans(to, v);
}
void solve(int v) {
  dfs(v, v);
  int ctr = getctr(v, v, sz[v]);
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= k; j++) dp1[i][j] = dp2[i][j] = 0;
  dp1[ctr][0] = 1;
  dp2[ctr][0] = 1;
  for (int len = 1; len <= k; len++) calc_dp(ctr, ctr, len, ctr);
  calc_ans(ctr, ctr);
  used[ctr] = 1;
  for (auto to : g[ctr])
    if (!used[to]) solve(to);
}
int main() {
  for (int i = 0; i < 80; i++) c[0][i] = 1;
  for (int i = 1; i < 80; i++)
    for (int j = 1; j <= i; j++)
      c[j][i] = (c[j - 1][i - 1] + c[j][i - 1]) % mod;
  scanf("%d%d%d", &n, &m, &k);
  if (k & 1) cout << 0, exit(0);
  for (int i = 1; i < n; i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    g[v].push_back(u);
    g[u].push_back(v);
  }
  solve(1);
  for (int i = 0; i <= k; i++) {
    ans1[i] = ans[i];
    ans[i] = 0;
  }
  n = m;
  for (int i = 0; i < maxn; i++) {
    used[i] = 0;
    g[i].clear();
  }
  for (int i = 1; i < n; i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    g[v].push_back(u);
    g[u].push_back(v);
  }
  solve(1);
  for (int i = 0; i <= k; i++) {
    ans2[i] = ans[i];
    ans[i] = 0;
  }
  for (int i = 0; i <= k; i++)
    add(ANS, 1ll * ans1[i] * ans2[k - i] % mod * c[i][k] % mod);
  cout << ANS;
}
