Problem: You are given two arrays a_0, a_1, …, a_{n - 1} and b_0, b_1, …, b_{m-1}, and an integer c.

Compute the following sum:

$$$∑_{i=0}^{n-1} ∑_{j=0}^{m-1} a_i b_j c^{i^2\,j^3}$$$

Since it's value can be really large, print it modulo 490019.

Input

First line contains three integers n, m and c (1 ≤ n, m ≤ 100 000, 1 ≤ c < 490019).

Next line contains exactly n integers a_i and defines the array a (0 ≤ a_i ≤ 1000).

Last line contains exactly m integers b_i and defines the array b (0 ≤ b_i ≤ 1000).

Output

Print one integer — value of the sum modulo 490019.

Examples

Input

2 2 3
0 1
0 1


Output

3


Input

3 4 1
1 1 1
1 1 1 1


Output

12


Input

2 3 3
1 2
3 4 5


Output

65652

Note

In the first example, the only non-zero summand corresponds to i = 1, j = 1 and is equal to 1 ⋅ 1 ⋅ 3^1 = 3.

In the second example, all summands are equal to 1.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
int ri() {
  char c = getchar();
  int x = 0, f = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) - '0' + c;
  return x * f;
}
const int L = 1024, N = 1e5 + 10, P = 490019, phi = P - 1;
const double pi = acos(-1.0);
struct cp {
  double r, i;
  cp(double _r = 0, double _i = 0) : r(_r), i(_i) {}
  cp operator+(const cp &a) { return cp(r + a.r, i + a.i); }
  cp operator-(const cp &a) { return cp(r - a.r, i - a.i); }
  cp operator*(const cp &a) { return cp(r * a.r - i * a.i, i * a.r + a.i * r); }
  cp operator/(const double &x) { return cp(r / x, i / x); }
  void operator*=(const cp &x) { *this = *this * x; }
  void operator/=(const double &x) { *this = *this / x; }
} A[2][L][L], B[2][L][L], w[L];
int R[L], pwc[phi], st[N], a[N], b[N], pw1[500], Lg1[500], pw2[500], Lg2[500],
    c, tp, n, m, Ans;
int Pow(int x, int k, int P) {
  int r = 1;
  for (; k; k >>= 1, x = 1LL * x * x % P)
    if (k & 1) r = 1LL * r * x % P;
  return r;
}
int Iv(int x, int P) { return Pow(x, P - 2, P); }
void Chi(int i, int &x, int &y, int &z) {
  x = i & 1;
  y = i % 491;
  z = i % 499;
}
int iChi(int a, int b, int c) {
  int x = 491LL * 499 * Iv(491 * 499, 2) % phi;
  int y = 2LL * 499 * Iv(2 * 499, 491) % phi;
  int z = 2LL * 491 * Iv(2 * 491, 499) % phi;
  return (1LL * a * x + 1LL * b * y + 1LL * c * z) % phi;
}
void Pre() {
  int x = 9;
  for (int i = 1; i < L; ++i) R[i] = R[i >> 1] >> 1 | (i & 1) << x;
  for (int i = 0; i < L; ++i)
    w[i] = cp(cos(2 * pi * i / L), sin(2 * pi * i / L));
  pwc[0] = 1;
  for (int i = 1; i < phi; ++i) pwc[i] = 1LL * pwc[i - 1] * c % P;
  pw1[0] = 1;
  for (int i = 1; i < 490; ++i) pw1[i] = pw1[i - 1] * 7 % 491, Lg1[pw1[i]] = i;
  pw2[0] = 1;
  for (int i = 1; i < 498; ++i) pw2[i] = pw2[i - 1] * 7 % 499, Lg2[pw2[i]] = i;
}
void DFT(cp *F, int ri) {
  for (int i = 1; i < L; ++i)
    if (i < R[i]) std::swap(F[i], F[R[i]]);
  for (int i = 1, d = L >> 1; i < L; i <<= 1, d >>= 1)
    for (int j = 0; j < L; j += i << 1) {
      cp *l = F + j, *r = F + j + i, *p = w, tp;
      for (int k = i; k--; ++l, ++r, p += d)
        tp = *r * *p, *r = *l - tp, *l = *l + tp;
    }
  if (!~ri) {
    for (int i = 1; i < L >> 1; ++i) std::swap(F[i], F[L - i]);
    for (int i = 0; i < L; ++i) F[i] /= L;
  }
}
void Tw_DFT(cp F[L][L], int ir) {
  for (int i = 0; i < L; ++i) DFT(F[i], ir);
  for (int i = 0; i < L; ++i) {
    static cp tp[L];
    for (int j = 0; j < L; ++j) tp[j] = F[j][i];
    DFT(tp, ir);
    for (int j = 0; j < L; ++j) F[j][i] = tp[j];
  }
}
void Solve0() {
  tp = 0;
  for (int i = 0; i < std::max(n, m); i += 491) st[++tp] = i;
  for (int i = 0; i < std::max(n, m); i += 499) st[++tp] = i;
  std::sort(st + 1, st + tp + 1);
  tp = std::unique(st + 1, st + tp + 1) - st - 1;
  for (int i = 0; i < n; ++i) {
    int i2 = 1LL * i * i % phi;
    long long sum = 0;
    for (int j = 1; j <= tp && st[j] < m; ++j) {
      int j3 = 1LL * st[j] * st[j] * st[j] % phi;
      sum += 1LL * a[i] * b[st[j]] * pwc[1LL * i2 * j3 % phi] % P;
    }
    Ans = (Ans + sum) % P;
  }
  for (int j = 0; j < m; ++j) {
    int j3 = 1LL * j * j * j % phi;
    long long sum = 0;
    for (int i = 1; i <= tp && st[i] < n; ++i) {
      int i2 = 1LL * st[i] * st[i] % phi;
      sum += 1LL * a[st[i]] * b[j] * pwc[1LL * i2 * j3 % phi] % P;
    }
    Ans = (Ans + sum) % P;
  }
  for (int i = 1; i <= tp && st[i] < n; ++i) {
    int i2 = 1LL * st[i] * st[i] % phi;
    long long sum = 0;
    for (int j = 1; j <= tp && st[j] < m; ++j) {
      int j3 = 1LL * st[j] * st[j] * st[j] % phi;
      sum += 1LL * a[st[i]] * b[st[j]] * pwc[1LL * i2 * j3 % phi] % P;
    }
    Ans = (Ans - sum) % P;
  }
}
int main() {
  n = ri();
  m = ri();
  c = ri();
  for (int i = 0; i < n; ++i) a[i] = ri();
  for (int i = 0; i < m; ++i) b[i] = ri();
  Pre();
  Solve0();
  for (int i = 0; i < n; ++i) {
    int x, y, z;
    Chi(i, x, y, z);
    if (!y || !z) continue;
    y = (Lg1[y] << 1) % 490;
    z = (Lg2[z] << 1) % 498;
    A[x][y][z].r += a[i];
    if (x) A[0][y][z].r += a[i];
  }
  for (int j = 0; j < m; ++j) {
    int x, y, z;
    Chi(j, x, y, z);
    if (!y || !z) continue;
    y = (Lg1[y] * 3) % 490;
    z = (Lg2[z] * 3) % 498;
    B[x][y][z].r += b[j];
    if (x) B[0][y][z].r += b[j];
  }
  Tw_DFT(A[0], 1);
  Tw_DFT(A[1], 1);
  Tw_DFT(B[0], 1);
  Tw_DFT(B[1], 1);
  for (int x = 0; x < 2; ++x)
    for (int y = 0; y < L; ++y)
      for (int z = 0; z < L; ++z) A[x][y][z] *= B[x][y][z];
  Tw_DFT(A[0], -1);
  Tw_DFT(A[1], -1);
  for (int x = 0; x < 2; ++x)
    for (int y = 0; y < L; ++y)
      for (int z = 0; z < L; ++z) {
        long long val = (long long)(A[x][y][z].r + 0.5);
        if (!x) val -= (long long)(A[1][y][z].r + 0.5);
        val %= P;
        Ans = (Ans + val * pwc[iChi(x, pw1[y % 490], pw2[z % 498])]) % P;
      }
  printf("%d\n", (Ans + P) % P);
  return 0;
}