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>
std::mt19937 rng(
    (int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 490019;
const int ms = 1 << 20;
const double PI = acosl(-1.0);
struct Complex {
  double real, imag;
  Complex(double a = 0, double b = 0) : real(a), imag(b) {}
  Complex operator+(const Complex &o) const {
    return Complex(real + o.real, imag + o.imag);
  }
  Complex operator-(const Complex &o) const {
    return Complex(real - o.real, imag - o.imag);
  }
  Complex operator*(const Complex &o) const {
    return Complex(real * o.real - imag * o.imag,
                   real * o.imag + imag * o.real);
  }
  Complex operator/(double o) const { return Complex(real / o, imag / o); }
  void operator*=(Complex o) { *this = *this * o; }
  void operator/=(double o) { real /= o, imag /= o; }
};
int bits[ms * 4];
void pre(int n) {
  int LOG = 0;
  while (1 << (LOG + 1) < n) {
    LOG++;
  }
  for (int i = 1; i < n; i++) {
    bits[i] = (bits[i >> 1] >> 1) | ((i & 1) << LOG);
  }
}
void fft(std::vector<Complex> &a, bool inv = false) {
  int n = a.size();
  for (int i = 0; i < n; i++) {
    int to = bits[i];
    if (to > i) {
      std::swap(a[to], a[i]);
    }
  }
  double angle = inv ? -PI : PI;
  for (int len = 1; len < n; len *= 2) {
    Complex delta(cosl(angle / len), sinl(angle / len));
    for (int i = 0; i < n; i += 2 * len) {
      Complex cur_root = 1;
      for (int j = 0; j < len; j++) {
        Complex u = a[i + j], v = a[i + j + len] * cur_root;
        a[i + j] = u + v;
        a[i + j + len] = u - v;
        cur_root *= delta;
      }
    }
  }
  if (inv) {
    for (int i = 0; i < n; i++) a[i] /= n;
  }
}
int fexp(long long x, long long e, long long mod) {
  long long ans = 1;
  for (; e > 0; e /= 2) {
    if (e & 1) ans = ans * x % mod;
    x = x * x % mod;
  }
  return (int)ans;
}
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
int g[ms], inv[ms];
int rs[ms], val[ms], p[3][ms];
int table[2][491][499];
int curt[3];
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int root = 7;
  int n, m, c;
  std::cin >> n >> m >> c;
  for (int i = 0; i < MOD - 1; i++) {
    g[i] = gcd(i, MOD - 1);
  }
  for (int i = 0; i < MOD - 1; i++) {
    rs[i] = fexp(root, i, MOD - 1);
  }
  std::vector<int> A(MOD - 1, 0);
  std::vector<int> B(MOD - 1, 0);
  for (int i = 0; i < n; i++) {
    int v;
    std::cin >> v;
    int pos = fexp(i, 2, MOD - 1);
    A[pos] += v;
    A[pos] %= MOD;
  }
  for (int i = 0; i < m; i++) {
    int v;
    std::cin >> v;
    int pos = fexp(i, 3, MOD - 1);
    B[pos] += v;
    B[pos] %= MOD;
  }
  std::vector<int> dvs;
  for (int i = 1; i <= MOD - 1; i++) {
    if ((MOD - 1) % i == 0) {
      dvs.push_back(i);
    }
  }
  int primes[] = {2, 491, 499};
  for (int i = 1; i < MOD - 1; i++) {
    table[i % 2][i % 491][i % 499] = i;
  }
  assert(2 * 491 * 499 == MOD - 1);
  for (int k = 0; k < 3; k++) {
    int pr = primes[k];
    for (int j = 1; rs[j] % pr != 1; j++) {
      p[k][rs[j] % pr] = j;
    }
    for (int j = 2; j < pr; j++) {
      assert(p[k][j] < MOD - 1 && p[k][j] != 0);
    }
  }
  long long ans = 0;
  std::vector<Complex> poly;
  for (auto f : dvs) {
    for (auto s : dvs) {
      int curG = lcm(f, s);
      if (curG == MOD - 1) {
        long long vals[2] = {0, 0};
        for (int i = 0; i < MOD - 1; i++) {
          if (g[i] == f && A[i]) {
            vals[0] += A[i];
          }
          if (g[i] == s && B[i]) {
            vals[1] += B[i];
          }
        }
        if (vals[0] && vals[1]) {
          ans = (ans + vals[0] * vals[1]) % MOD;
        }
        continue;
      }
      int tot = (MOD - 1) / curG;
      int size = 1;
      int mx1 = -1, mx2 = -1;
      for (int i = 0; i < MOD - 1; i++) {
        int pos = 0;
        for (int j = 1; j < 3; j++) {
          if (tot % primes[j] != 0) continue;
          pos = pos * (2 * primes[j] - 1) + p[j][i % primes[j]];
        }
        if (g[i] == f && A[i] && mx1 < pos) mx1 = pos;
        if (g[i] == s && B[i] && mx2 < pos) mx2 = pos;
      }
      if (mx1 == -1 || mx2 == -1) continue;
      while (size - 1 < mx1 + mx2) size += size;
      assert(size <= ms);
      poly.assign(size, 0);
      for (int i = 0; i < MOD - 1; i++) {
        int pos = 0;
        for (int j = 1; j < 3; j++) {
          if (tot % primes[j] != 0) continue;
          pos = pos * (2 * primes[j] - 1) + p[j][i % primes[j]];
        }
        if (g[i] == f && A[i]) {
          int nxt = int(poly[pos].real + 0.5);
          nxt = (nxt + A[i] + MOD) % MOD;
          poly[pos].real = nxt;
        }
        if (g[i] == s && B[i]) {
          assert(pos <= mx2);
          int nxt = int(poly[pos].imag + 0.5);
          nxt = (nxt + B[i] + MOD) % MOD;
          poly[pos].imag = nxt;
        }
      }
      pre(size);
      fft(poly);
      for (int i = 0; i < size; i++) {
        poly[i] *= poly[i];
      }
      fft(poly, true);
      long long wtf = 0;
      for (int i = 0; i < size; i++) {
        int cur = (int)((long long)(poly[i].imag + 0.5) / 2 % MOD);
        if (cur == 0) continue;
        int v = i;
        for (int j = 2; j >= 0; j--) {
          if (tot % primes[j] == 0) {
            curt[j] = v % (2 * primes[j] - 1) % (primes[j] - 1);
            v /= 2 * primes[j] - 1;
            curt[j] = rs[curt[j]] % primes[j];
          } else {
            curt[j] = 0;
          }
        }
        v = table[curt[0]][curt[1]][curt[2]];
        v = fexp(c, v, MOD);
        wtf = (wtf + (long long)v * cur) % MOD;
      }
      ans = (ans + wtf) % MOD;
    }
  }
  ans = (ans % MOD + MOD) % MOD;
  std::cout << ans << std::endl;
}