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>
const int N = 1e5 + 5, MOD = 490019, P[2] = {491, 499}, G[2] = {2, 7};
inline int add(int a, const int &b) {
  a += b;
  return a >= MOD ? a - MOD : a;
}
inline int sub(int a, const int &b) {
  a -= b;
  return a < 0 ? a + MOD : a;
}
inline int mul(const int &a, const int &b) { return 1ll * a * b % MOD; }
inline int &inc(int &a, const int &b) { return a = add(a, b); }
inline int &dec(int &a, const int &b) { return a = sub(a, b); }
inline int &pro(int &a, const int &b) { return a = mul(a, b); }
inline int qpow(int a, int b) {
  int c = 1;
  for (; b; b >>= 1, pro(a, a))
    if (b & 1) pro(c, a);
  return c;
}
const int lgL = 10, L = 1 << lgL;
const double pi = acos(-1);
struct Com {
  double x, y;
  inline Com(double _x = 0, double _y = 0) {
    x = _x;
    y = _y;
  }
  inline Com operator+(const Com &t) const { return Com(x + t.x, y + t.y); }
  inline Com operator+(const double &t) const { return Com(x + t, y); }
  inline Com &operator+=(const double &t) { return *this = *this + t; }
  inline Com operator-(const Com &t) const { return Com(x - t.x, y - t.y); }
  inline Com operator*(const Com &t) const {
    return Com(x * t.x - y * t.y, x * t.y + y * t.x);
  }
  inline Com operator*(const double &t) const { return Com(x * t, y * t); }
  inline Com operator/(const double &t) const { return Com(x / t, y / t); }
  inline Com &operator/=(const double &t) { return *this = *this / t; }
} w[2][1 << lgL];
const int Inv[3] = {1, 399, 343};
inline void exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}
inline int inv(int a, int b) {
  a %= b;
  int x, y;
  exgcd(a, b, x, y);
  ((x %= b) += b) %= b;
  return x;
}
inline int crt(int x, int y, int z) {
  int ret = 0;
  ret += x * Inv[0] * P[0] * P[1] % (MOD - 1);
  ret += y * Inv[1] * 2 * P[1] % (MOD - 1);
  ret += z * Inv[2] * 2 * P[0] % (MOD - 1);
  return ret % (MOD - 1);
}
int lg[2][L], e[2][L];
int pw[MOD - 1];
int n, m, c;
inline void pre() {
  for (int i = 1; i < 1 << lgL; i <<= 1) {
    w[0][i] = w[1][i] = Com(1, 0);
    for (int j = 1; j < i; j++)
      w[0][i + j] = Com(cos(j * pi / i), sin(j * pi / i)),
               w[1][i + j] = Com(cos(j * pi / i), -sin(j * pi / i));
  }
  for (int k = 0; k < 2; k++)
    for (int i = 0, cur = 1; i < P[k] - 1; i++) {
      lg[k][cur] = i;
      e[k][i] = cur;
      (cur *= G[k]) %= P[k];
    }
  pw[0] = 1;
  for (int i = 1; i < MOD - 1; i++) pw[i] = mul(c, pw[i - 1]);
}
int rev[1 << lgL];
inline void fft(Com *f, const int opt, const int l = L) {
  for (int i = 0; i < l; i++) {
    rev[i] = rev[i >> 1] >> 1 | (i & 1) * (l >> 1);
    if (i < rev[i]) std::swap(f[i], f[rev[i]]);
  }
  for (int i = 1; i < l; i <<= 1)
    for (int j = 0; j < l; j += i << 1)
      for (int k = 0; k < i; k++) {
        Com x = f[j + k], y = f[i + j + k] * w[opt][i + k];
        f[j + k] = x + y;
        f[i + j + k] = x - y;
      }
  if (opt)
    for (int i = 0; i < l; i++) f[i] /= l;
}
inline void fft(Com (*F)[L], const int opt, const int l = L) {
  static Com f[L];
  for (int i = 0; i < l; i++) {
    for (int j = 0; j < l; j++) f[j] = F[j][i];
    fft(f, opt, l);
    for (int j = 0; j < l; j++) F[j][i] = f[j];
  }
  for (int i = 0; i < l; i++) fft(F[i], opt, l);
}
Com A[2][L][L], B[2][L][L], F[2][L][L];
int a[N], b[N];
int main() {
  scanf("%d%d%d", &n, &m, &c);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 0; i < m; i++) scanf("%d", &b[i]);
  pre();
  std::vector<int> va, vb;
  for (int i = 0; i < n; i++) {
    if (i % P[0] && i % P[1]) {
      A[i & 1][2 * lg[0][i % P[0]] % (P[0] - 1)]
       [2 * lg[1][i % P[1]] % (P[1] - 1)] += a[i];
    } else
      va.push_back(i);
  }
  for (int i = 0; i < m; i++) {
    if (i % P[0] && i % P[1]) {
      B[i & 1][3 * lg[0][i % P[0]] % (P[0] - 1)]
       [3 * lg[1][i % P[1]] % (P[1] - 1)] += b[i];
    } else
      vb.push_back(i);
  }
  fft(A[0], 0);
  fft(A[1], 0);
  fft(B[0], 0);
  fft(B[1], 0);
  for (int i = 0; i < L; i++)
    for (int j = 0; j < L; j++) {
      F[0][i][j] = A[0][i][j] * B[0][i][j] + A[0][i][j] * B[1][i][j] +
                   A[1][i][j] * B[0][i][j];
      F[1][i][j] = A[1][i][j] * B[1][i][j];
    }
  fft(F[0], 1);
  fft(F[1], 1);
  int ans = 0;
  for (int k = 0; k < 2; k++)
    for (int i = 0; i < L; i++)
      for (int j = 0; j < L; j++)
        inc(ans, mul(pw[crt(k, e[0][i % (P[0] - 1)], e[1][j % (P[1] - 1)])],
                     (long long)(F[k][i][j].x + 0.5) % MOD));
  for (int i = 0, sz = va.size(); i < sz; i++) {
    const int id = va[i], id2 = 1ll * id * id % (MOD - 1);
    for (int j = 0; j < m; j++)
      inc(ans, mul(pw[1ll * id2 * j % (MOD - 1) * j * j % (MOD - 1)],
                   mul(a[id], b[j])));
  }
  for (int i = 0, sz = vb.size(); i < sz; i++) {
    const int id = vb[i], id3 = 1ll * id * id * id % (MOD - 1);
    for (int j = 0; j < n; j++)
      if (j % P[0] && j % P[1])
        inc(ans, mul(pw[1ll * j * j * id3 % (MOD - 1)], mul(b[id], a[j])));
  }
  printf("%d\n", ans);
  return 0;
}