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>
using namespace std;
const int maxn = 1e6 + 10;
const int maxl = 1024;
const int mod = 490019, P1 = 491, g1 = 2, P2 = 499, g2 = 7;
int ta[2][maxl][maxl], tb[2][maxl][maxl], a[maxn], b[maxn];
int n, m, c;
int ans[maxn];
int LogP1[maxn], LogP2[maxn], posP1[maxn], posP2[maxn], merg[2][maxl][maxl];
complex<double> operator/(complex<double> a, double b) {
  return complex<double>(a.real() / b, a.imag() / b);
}
inline void add(int &x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}
inline void sub(int &x, int y) {
  x -= y;
  if (x < 0) {
    x += mod;
  }
}
inline int mul(int x, int y) { return (int)((long long)x * y % mod); }
inline int power(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) {
      res = mul(res, x);
    }
    x = mul(x, x);
    y >>= 1;
  }
  return res;
}
inline int inv(int a) {
  int b = mod, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  if (u < 0) {
    u += mod;
  }
  return u;
}
namespace fft {
const double Pi = acos(-1.0);
int base = 1;
vector<int> rev = {0, 1};
vector<complex<double> > roots = {complex<double>(1, 0), complex<double>(1, 0)};
void ensure_base(int nbase) {
  if (nbase <= base) {
    return;
  }
  rev.resize(1 << nbase);
  for (int i = 0; i < 1 << nbase; ++i) {
    rev[i] = rev[i >> 1] >> 1 | (i & 1) << (nbase - 1);
  }
  roots.resize(1 << nbase);
  while (base < nbase) {
    complex<double> z(cos(Pi / (1 << base)), sin(Pi / (1 << base)));
    for (int i = 1 << (base - 1); i < 1 << base; ++i) {
      roots[i << 1] = roots[i];
      roots[i << 1 | 1] = roots[i] * z;
    }
    ++base;
  }
}
void dft(vector<complex<double> > &a) {
  int n = a.size(), zeros = __builtin_ctz(n);
  ensure_base(zeros);
  int shift = base - zeros;
  for (int i = 0; i < n; ++i) {
    if (i < rev[i] >> shift) {
      swap(a[i], a[rev[i] >> shift]);
    }
  }
  for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j += i << 1) {
      for (int k = 0; k < i; ++k) {
        complex<double> x = a[j + k], y = a[j + k + i] * roots[i + k];
        a[j + k] = x + y;
        a[j + k + i] = x - y;
      }
    }
  }
}
}  // namespace fft
using fft::dft;
void init() {
  for (int i = 0, t = 1; i <= P1 - 2; i++, t = t * g1 % P1) {
    posP1[i] = t, LogP1[t] = i;
  }
  for (int i = 0, t = 1; i <= P2 - 2; i++, t = t * g2 % P2) {
    posP2[i] = t, LogP2[t] = i;
  }
  for (int i = 0; i < mod; i++) merg[i & 1][i % P1][i % P2] = i;
}
void solve() {
  static complex<double> va[2][maxl][maxl], vb[2][maxl][maxl],
      res[2][maxl][maxl];
  for (int t = 0; t <= 1; t++) {
    for (int j = 0; j < maxl; j++) {
      vector<complex<double> > A(maxl), B(maxl);
      for (int k = 0; k < maxl; k++) {
        A[k] = complex<double>(ta[t][j][k], 0);
        B[k] = complex<double>(tb[t][j][k], 0);
      }
      dft(A);
      dft(B);
      for (int k = 0; k < maxl; k++) {
        va[t][j][k] = A[k];
        vb[t][j][k] = B[k];
      }
    }
  }
  for (int t = 0; t <= 1; t++) {
    for (int k = 0; k < maxl; k++) {
      vector<complex<double> > A(maxl), B(maxl);
      for (int j = 0; j < maxl; j++) {
        A[j] = va[t][j][k];
        B[j] = vb[t][j][k];
      }
      dft(A);
      dft(B);
      for (int j = 0; j < maxl; j++) {
        va[t][j][k] = A[j];
        vb[t][j][k] = B[j];
      }
    }
  }
  for (int j = 0; j < maxl; j++) {
    for (int k = 0; k < maxl; k++) {
      va[0][j][k] += va[1][j][k];
      vb[0][j][k] += vb[1][j][k];
      res[0][j][k] = va[0][j][k] * vb[0][j][k];
      res[1][j][k] = va[1][j][k] * vb[1][j][k];
    }
  }
  for (int t = 0; t <= 1; t++) {
    for (int j = 0; j < maxl; j++) {
      vector<complex<double> > A(maxl);
      for (int k = 0; k < maxl; k++) {
        A[k] = res[t][j][k];
      }
      dft(A);
      reverse(A.begin() + 1, A.end());
      for (int k = 0; k < maxl; k++) res[t][j][k] = A[k] / maxl;
    }
  }
  for (int t = 0; t <= 1; t++) {
    for (int k = 0; k < maxl; k++) {
      vector<complex<double> > A(maxl);
      for (int j = 0; j < maxl; j++) {
        A[j] = res[t][j][k];
      }
      dft(A);
      reverse(A.begin() + 1, A.end());
      for (int j = 0; j < maxl; j++) res[t][j][k] = A[j] / maxl;
    }
  }
  for (int j = 0; j < maxl; j++) {
    for (int k = 0; k < maxl; k++) {
      res[0][j][k] -= res[1][j][k];
    }
  }
  for (int t = 0; t <= 1; t++)
    for (int j = 0; j < maxl; j++)
      for (int k = 0; k < maxl; k++)
        add(ans[merg[t][posP1[j % (P1 - 1)]][posP2[k % (P2 - 1)]]],
            (long long)(res[t][j][k].real() + 0.5) % mod);
  for (int i = 0; i < n; i += P1) {
    for (int j = 0; j < m; j++) {
      long long id = (long long)i * i % (mod - 1) * j % (mod - 1) * j %
                     (mod - 1) * j % (mod - 1);
      add(ans[id], mul(a[i], b[j]));
    }
  }
  for (int i = 0; i < n; i += P2) {
    if (i % P1 == 0) continue;
    for (int j = 0; j < m; j++) {
      long long id = (long long)i * i % (mod - 1) * j % (mod - 1) * j %
                     (mod - 1) * j % (mod - 1);
      add(ans[id], mul(a[i], b[j]));
    }
  }
  for (int j = 0; j < m; j += P1) {
    for (int i = 0; i < n; i++) {
      if (i % P1 == 0 || i % P2 == 0) continue;
      long long id = (long long)i * i % (mod - 1) * j % (mod - 1) * j %
                     (mod - 1) * j % (mod - 1);
      add(ans[id], mul(a[i], b[j]));
    }
  }
  for (int j = 0; j < m; j += P2) {
    if (j % P1 == 0) continue;
    for (int i = 0; i < n; i++) {
      if (i % P1 == 0 || i % P2 == 0) continue;
      long long id = (long long)i * i % (mod - 1) * j % (mod - 1) * j %
                     (mod - 1) * j % (mod - 1);
      add(ans[id], mul(a[i], b[j]));
    }
  }
  int r = 0, powc = 1;
  for (int i = 0; i < mod; i++) add(r, mul(ans[i], powc)), powc = mul(powc, c);
  cout << r << endl;
}
int main() {
  init();
  scanf("%d %d %d", &n, &m, &c);
  for (int i = 0; i < n; i++) {
    long long x = (long long)i * i;
    scanf("%d", &a[i]);
    if (x % P1 == 0 || x % P2 == 0) continue;
    add(ta[x & 1][LogP1[x % P1]][LogP2[x % P2]], a[i]);
  }
  for (int i = 0; i < m; i++) {
    long long x = (long long)i * i * i;
    scanf("%d", &b[i]);
    if (x % P1 == 0 || x % P2 == 0) continue;
    add(tb[x & 1][LogP1[x % P1]][LogP2[x % P2]], b[i]);
  }
  solve();
}