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;
namespace FFT {
const double TAU = 2 * acos(-1.0);
int base;
complex<double> w[1 << 20];
int rev[1 << 20];
int setBase(int nbase) {
  int i, j;
  base = nbase;
  for (i = 0; i < (1 << base); i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (base - 1));
  w[0] = complex<double>(0, 0), w[1] = complex<double>(1, 0);
  for (i = 1; i < nbase; i++) {
    double a = TAU / ((1 << (i + 1)));
    for (j = (1 << (i - 1)); j < (1 << i); j++) {
      w[j << 1] = w[j];
      double a2 = a * (((j << 1) | 1) - (1 << i));
      w[(j << 1) | 1] = complex<double>(cos(a2), sin(a2));
    }
  }
  return 0;
}
int FFT(vector<complex<double> > &a) {
  int i, j, k;
  int l = 0;
  while ((1 << l) < a.size()) l++;
  int s = base - l;
  for (i = 0; i < a.size(); i++) {
    if (i < (rev[i] >> s)) swap(a[i], a[rev[i] >> s]);
  }
  for (k = 1; k < a.size(); k <<= 1) {
    for (i = 0; i < a.size(); i += (k << 1)) {
      for (j = 0; j < k; j++) {
        complex<double> z = a[i + j + k] * w[j + k];
        a[i + j + k] = a[i + j] - z, a[i + j] = a[i + j] + z;
      }
    }
  }
  return 0;
}
template <typename T>
vector<T> multiply(vector<T> A, vector<T> B) {
  int i, n = 1;
  while (n < A.size() + B.size() - 1) n <<= 1;
  vector<complex<double> > a(n, 0);
  for (i = 0; i < n; i++)
    a[i] =
        complex<double>((i < A.size()) ? A[i] : 0, (i < B.size()) ? B[i] : 0);
  FFT(a);
  complex<double> r(0, -0.25 / n);
  for (i = 0; i <= (n >> 1); i++) {
    int j = (n - i) & (n - 1);
    complex<double> z = (a[j] * a[j] - conj(a[i] * a[i])) * r;
    if (i != j) a[j] = (a[i] * a[i] - conj(a[j] * a[j])) * r;
    a[i] = z;
  }
  FFT(a);
  vector<T> ans(A.size() + B.size() - 1);
  for (i = 0; i < A.size() + B.size() - 1; i++) ans[i] = a[i].real() + 0.5;
  return ans;
}
}  // namespace FFT
namespace NTT {
int mbase, base, root;
int w[1 << 20];
int rev[1 << 20];
int modPow(int b, int e) {
  int r = 1;
  while (e > 0) {
    if (e & 1) r = ((long long int)r * b) % 998244353;
    e >>= 1;
    b = ((long long int)b * b) % 998244353;
  }
  return r;
}
int setBase(int nbase) {
  int i, j;
  mbase = 1;
  while (!(998244353 & (1 << mbase))) mbase++;
  root = 2;
  while ((modPow(root, 1 << mbase) != 1) ||
         (modPow(root, 1 << (mbase - 1)) == 1))
    root++;
  base = nbase;
  for (i = 0; i < (1 << base); i++)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (base - 1));
  w[0] = 0, w[1] = 1;
  for (i = 1; i < nbase; i++) {
    int z = modPow(root, 1 << (mbase - i - 1));
    for (j = (1 << (i - 1)); j < (1 << i); j++)
      w[j << 1] = w[j], w[(j << 1) | 1] = ((long long int)w[j] * z) % 998244353;
  }
  return 0;
}
int FFT(vector<int> &a, int inv) {
  int i, j, k;
  int l = 0;
  while ((1 << l) < a.size()) l++;
  int s = base - l;
  for (i = 0; i < a.size(); i++) {
    if (i < (rev[i] >> s)) swap(a[i], a[rev[i] >> s]);
  }
  for (k = 1; k < a.size(); k <<= 1) {
    for (i = 0; i < a.size(); i += (k << 1)) {
      for (j = 0; j < k; j++) {
        int z = ((long long int)a[i + j + k] * w[j + k]) % 998244353;
        a[i + j + k] = a[i + j] - z, a[i + j] += z;
        if (a[i + j + k] < 0) a[i + j + k] += 998244353;
        if (a[i + j] >= 998244353) a[i + j] -= 998244353;
      }
    }
  }
  return 0;
}
vector<int> multiply(vector<int> A, vector<int> B) {
  int i, n = 1;
  while (n < A.size() + B.size() - 1) n <<= 1;
  vector<int> a(n, 0), b(n, 0);
  for (i = 0; i < A.size(); i++) a[i] = A[i];
  for (i = 0; i < B.size(); i++) b[i] = B[i];
  FFT(a, 0), FFT(b, 0);
  int x = modPow(n, 998244353 - 2);
  for (i = 0; i < n; i++)
    a[i] = ((((long long int)a[i] * b[i]) % 998244353) * x) % 998244353;
  reverse(a.begin() + 1, a.end()), FFT(a, 1), a.resize(A.size() + B.size() - 1);
  return a;
}
}  // namespace NTT
vector<long long int> A, B;
int main() {
  int i;
  int n, m, c, x;
  scanf("%d %d %d", &n, &m, &c);
  A.resize(490018), B.resize(490018);
  for (i = 0; i < n; i++)
    scanf("%d", &x), A[((long long int)i * i) % 490018] += x;
  for (i = 0; i < m; i++)
    scanf("%d", &x), B[((long long int)i * i * i) % 490018] += x;
  int invc = 1;
  int b = c, e = 490019 - 2;
  while (e > 0) {
    if (e & 1) invc = ((long long int)invc * b) % 490019;
    e >>= 1;
    b = ((long long int)b * b) % 490019;
  }
  for (i = 0; i < 490018; i++) {
    if (A[i] > 0) {
      A[i] %= 490019;
      int b = invc, e = ((long long int)i * (i - 1) / 2) % 490018;
      while (e > 0) {
        if (e & 1) A[i] = (A[i] * b) % 490019;
        e >>= 1;
        b = ((long long int)b * b) % 490019;
      }
    }
    if (B[i] > 0) {
      B[i] %= 490019;
      int b = invc, e = ((long long int)i * (i - 1) / 2) % 490018;
      while (e > 0) {
        if (e & 1) B[i] = (B[i] * b) % 490019;
        e >>= 1;
        b = ((long long int)b * b) % 490019;
      }
    }
  }
  int ans = 0;
  FFT::setBase(20);
  vector<long long int> C = FFT::multiply(A, B);
  vector<int> A2, B2;
  for (i = 0; i < 490018; i++) A2.push_back(A[i]), B2.push_back(B[i]);
  NTT::setBase(20);
  vector<int> C2 = NTT::multiply(A2, B2);
  for (i = 0; i < C.size(); i++) {
    int t = (C2[i] - (C[i] % 998244353) + 998244353) % 998244353;
    if (t < 998244353 / 2)
      C[i] += t;
    else
      C[i] += t - 998244353;
    C[i] %= 490019;
    int b = c, e = ((long long int)i * (i - 1) / 2) % 490018;
    while (e > 0) {
      if (e & 1) C[i] = (C[i] * b) % 490019;
      e >>= 1;
      b = ((long long int)b * b) % 490019;
    }
    ans += C[i], ans %= 490019;
  }
  printf("%d\n", ans);
  return 0;
}