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>
#pragma GCC optimize("-O3")
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
void Out(int x) {
  if (x > 9) Out(x / 10);
  putchar('0' + x % 10);
}
int gcd(int x, int y) {
  if (!y) return x;
  return gcd(y, x % y);
}
long long qpow(long long x, long long y, long long P) {
  long long re = 1;
  while (y) {
    if (y & 1) re = re * x % P;
    x = x * x % P;
    y >>= 1;
  }
  return re;
}
long long likegcd(long long a, long long b, long long c, long long n) {
  long long re, p;
  if (c < 0) return likegcd(-a, -b, -c, n);
  if (a < 0 || b < 0) {
    re = likegcd(a % c + c, b % c + c, c, n);
    re += n * (n + 1) / 2 * ((a / c) - 1);
    re += (n + 1) * ((b / c) - 1);
    return re;
  }
  if (a == 0) {
    re = (b / c) * (n + 1);
    return re;
  }
  if (a >= c || b >= c) {
    p = likegcd(a % c, b % c, c, n);
    re = n * (n + 1) / (long long)2 * (a / c);
    re += (b / c) * (n + 1);
    re += p;
    return re;
  }
  long long m = (a * n + b) / c;
  p = likegcd(c, c - b - 1, a, m - 1);
  re = -p + n * m;
  return re;
}
const double eps = 1e-6;
const double PI = acos(-1);
const int N = 5e4 + 10;
const long long P = 490019;
const long long pa = 491, pb = 499;
const long long ra = 2, rb = 7;
struct V {
  double x, y;
  V(double _x = 0, double _y = 0) {
    x = _x;
    y = _y;
  }
};
V operator+(V a, V b) { return V(a.x + b.x, a.y + b.y); }
V operator-(V a, V b) { return V(a.x - b.x, a.y - b.y); }
V operator*(V a, V b) {
  return V(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
V operator/(V a, double b) { return V(a.x / b, a.y / b); }
struct FFT {
  int n;
  int rev[2050];
  void init() {
    int k = 10;
    n = 1024;
    for (int i = 0; i < n; ++i) {
      int t = 0;
      for (int j = 0; j < k; ++j)
        if (i & (1 << j)) t |= (1 << (k - j - 1));
      rev[i] = t;
    }
  }
  void DFT(V *a, int flag) {
    for (int i = 0; i < n; ++i)
      if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int l = 2; l <= n; l <<= 1) {
      int m = l >> 1;
      V wn(cos((double)2 * PI / l), (double)flag * sin(2 * PI / l));
      for (V *p = a; p != a + n; p += l) {
        V w(1, 0);
        for (int k = 0; k < m; ++k) {
          V t = w * p[k + m];
          p[k + m] = p[k] - t;
          p[k] = p[k] + t;
          w = w * wn;
        }
      }
    }
    if (flag == -1)
      for (int i = 0; i < n; ++i) {
        a[i].x /= (double)n;
        a[i].y /= (double)n;
      }
  }
} fft;
int n, m;
long long c;
long long sa[P + 10], sb[P + 10];
long long C[P + 10];
vector<int> pos;
long long La[2000], Lb[2000];
int f[2][1100][1100];
V A[2][1100][1100], B[2][1100][1100];
V a[1100], b[1100];
int main() {
  fft.init();
  cin >> n >> m >> c;
  int x;
  for (long long i = 0; i < n; ++i) {
    scanf("%d", &x);
    sa[i * i % (P - 1)] += x;
  }
  for (long long i = 0; i < m; ++i) {
    scanf("%d", &x);
    sb[i * i * i % (P - 1)] += x;
  }
  for (int i = 0; i <= P - 2; ++i)
    if (i % pa == 0 || i % pb == 0) pos.push_back(i);
  for (int i = 0; i <= P - 2; ++i)
    if (sb[i])
      for (int j = 0; j < pos.size(); ++j)
        if (sa[pos[j]]) {
          x = (long long)i * (long long)pos[j] % (P - 1);
          C[x] = (C[x] + sb[i] * sa[pos[j]]) % P;
        }
  for (int i = 0; i <= P - 2; ++i)
    if (sa[i] && i % pa && i % pb)
      for (int j = 0; j < pos.size(); ++j)
        if (sb[pos[j]]) {
          x = (long long)i * (long long)pos[j] % (P - 1);
          C[x] = (C[x] + sa[i] * sb[pos[j]]) % P;
        }
  long long y = 1;
  for (int i = 0; i <= pa - 2; ++i) La[y] = i, y = y * ra % pa;
  y = 1;
  for (int i = 0; i <= pb - 2; ++i) Lb[y] = i, y = y * rb % pb;
  for (int i = 0; i <= P - 1; ++i)
    if (i % pa && i % pb) {
      int X = i % 2, Y = La[i % pa], Z = Lb[i % pb];
      A[X][Y][Z].x = sa[i] % P;
      B[X][Y][Z].x = sb[i] % P;
      f[X][Y][Z] = i;
    }
  for (int i = 0; i < pa; ++i)
    for (int j = 0; j < pb; ++j)
      A[0][i][j] = A[0][i][j] + A[1][i][j],
      B[0][i][j] = B[0][i][j] + B[1][i][j];
  for (int i = 0; i <= 1; ++i)
    for (int j = 0; j < pa; ++j) {
      fft.DFT(A[i][j], 1);
    }
  for (int i = 0; i <= 1; ++i)
    for (int j = 0; j < pa; ++j) fft.DFT(B[i][j], 1);
  for (int i = 0; i <= 1; ++i)
    for (int j = 0; j < fft.n; ++j) {
      for (int k = 0; k < fft.n; ++k) a[k] = A[i][k][j], b[k] = B[i][k][j];
      fft.DFT(a, 1);
      fft.DFT(b, 1);
      for (int k = 0; k < fft.n; ++k) a[k] = a[k] * b[k];
      fft.DFT(a, -1);
      for (int k = 0; k < fft.n; ++k) A[i][k][j] = a[k];
    }
  for (int i = 0; i <= 1; ++i)
    for (int j = 0; j < fft.n; ++j) fft.DFT(A[i][j], -1);
  for (int i = 0; i < fft.n; ++i)
    for (int j = 0; j < fft.n; ++j) A[0][i][j] = A[0][i][j] - A[1][i][j];
  for (int i = 0; i <= 1; ++i)
    for (int j = 0; j < fft.n; ++j)
      for (int k = 0; k < fft.n; ++k) {
        (C[f[i][j % (pa - 1)][k % (pb - 1)]] +=
         (long long)(A[i][j][k].x + 0.5)) %= P;
      }
  y = 1;
  long long ans = 0;
  for (int i = 0; i <= P - 1; ++i) {
    ans = (ans + y * C[i]) % P;
    y = y * c % P;
  }
  cout << ans << endl;
  return 0;
}