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;
inline int read() {
  int n = 0;
  char c;
  for (c = getchar(); c < '0' || c > '9'; c = getchar())
    ;
  for (; c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - 48;
  return n;
}
const int N = 1 << 20, mo = 490019, mo1 = mo - 1;
const int mn1 = 491, mn2 = 499, mn = mn1 * mn2, g1 = 2, g2 = 7, r1 = 187 * mn1,
          r2 = 307 * mn2;
const double pi = acos(-1);
int i, l, j, k, p, n, m, a[N], b[N], c;
int id1[mn1], id2[mn2], f1[mn1], f2[mn2];
int A1[2][2][mn1], B1[2][2][mn1], A2[2][2][mn2], B2[2][2][mn2];
long long C1[2][mn1], C2[2][mn2], ans, z[N];
struct Z {
  double x, y;
  Z operator+(const Z &b) { return (Z){x + b.x, y + b.y}; }
  Z operator-(const Z &b) { return (Z){x - b.x, y - b.y}; }
  Z operator*(const Z &b) { return (Z){x * b.x - y * b.y, x * b.y + y * b.x}; }
  void operator/=(const double &a) { x /= a, y /= a; }
  Z conj() { return (Z){x, -y}; }
} w[N], A[N], B[N], C[N];
int f[N];
void mod(int &x) { x -= x >= mo ? mo : 0; }
int qs(int x, int y, int mo) {
  int s = 1;
  for (; y; y >>= 1, x = (long long)x * x % mo)
    if (y & 1) s = (long long)s * x % mo;
  return s;
}
void pre() {
  for (int i = 1; i < N; i++) f[i] = f[i >> 1] >> 1 | (i & 1 ? N >> 1 : 0);
  for (int i = 1, st = 0; i < N; i <<= 1) {
    for (int k = 0; k < i; k++) w[st++] = (Z){cos(k * pi / i), sin(k * pi / i)};
  }
}
void dft(Z *a, bool sig) {
  int i;
  for (i = 0; i <= N - 1; i++)
    if (i < f[i]) swap(a[i], a[f[i]]);
  for (int i = 1, st = 0; i < N; st += i, i <<= 1) {
    for (int j = 0; j < N; j += i << 1) {
      for (int k = 0, o = st; k < i; k++, o++) {
        Z u = a[j + k], v = a[i + j + k] * w[o];
        a[j + k] = u + v, a[i + j + k] = u - v;
      }
    }
  }
  if (sig) {
    reverse(a + 1, a + N);
    for (i = 0; i <= N - 1; i++) a[i] /= N;
  }
}
int main() {
  n = read(), m = read(), c = read();
  for (i = 0; i <= n - 1; i++) j = (long long)i * i % mo1, mod(a[j] += read());
  for (i = 0; i <= m - 1; i++)
    j = (long long)i * i * i % mo1, mod(b[j] += read());
  for (i = g1, j = 1; i != 1; i = i * g1 % mn1, j++) id1[i] = j, f1[j] = i;
  for (i = g2, j = 1; i != 1; i = i * g2 % mn2, j++) id2[i] = j, f2[j] = i;
  f1[0] = f2[0] = 1;
  for (i = 0; i <= mo1; i++) {
    int x = a[i], y = b[i];
    if (!x && !y) continue;
    l = i & 1, j = i % mn1, k = i % mn2;
    mod(A1[l][!k][j] += x), mod(B1[l][!k][j] += y);
    if (k) mod(A2[l][!j][k] += x), mod(B2[l][!j][k] += y);
    if (j && k) {
      j = id1[j] << 10 | id2[k];
      if (!l)
        A[j].x = x, B[j].x = y;
      else
        A[j].y = x, B[j].y = y;
    }
  }
  pre();
  dft(A, 0), dft(B, 0);
  for (i = 0; i <= N - 1; i++) {
    Z x = A[i], y = A[i == 0 ? 0 : N - i];
    Z a0 = (x + y.conj()) * (Z){0.5, 0}, a1 = (x - y.conj()) * (Z){0, -0.5};
    x = B[i], y = B[i == 0 ? 0 : N - i];
    Z b0 = (x + y.conj()) * (Z){0.5, 0}, b1 = (x - y.conj()) * (Z){0, -0.5};
    C[i] = a0 * (b0 + b1) + a1 * b0 + a1 * b1 * (Z){0, 1};
  }
  dft(C, 1);
  for (p = 0; p <= N - 1; p++) {
    i = (p >> 10) % (mn1 - 1), j = (p & 1023) % (mn2 - 1);
    k = (long long)(f1[i] * r2 + f2[j] * r1) % mn * (mn + 1) % mo1;
    z[k] += (long long)round(C[p].x),
        z[(mn + k) % mo1] += (long long)round(C[p].y);
  }
  for (i = 0; i <= 1; i++)
    for (j = 0; j <= 1; j++)
      if (i | j) {
        for (l = 0; l <= mn1 - 1; l++) {
          long long a0 = A1[0][i][l], a1 = A1[1][i][l];
          for (k = 0, p = 0; k < mn1; k++, p += l, p -= p >= mn1 ? mn1 : 0) {
            int b0 = B1[0][j][k], b1 = B1[1][j][k];
            C1[0][p] += (a0 * (b0 + b1) + a1 * b0) % mo,
                C1[1][p] += a1 * b1 % mo;
          }
        }
        for (l = 1; l <= mn2 - 1; l++) {
          long long a0 = A2[0][i][l], a1 = A2[1][i][l];
          for (k = 1, p = l; k < mn2; k++, p += l, p -= p >= mn2 ? mn2 : 0) {
            int b0 = B2[0][j][k], b1 = B2[1][j][k];
            C2[0][p] += (a0 * (b0 + b1) + a1 * b0) % mo,
                C2[1][p] += a1 * b1 % mo;
          }
        }
      }
  for (i = 0; i <= mn1 - 1; i++) {
    k = (long long)i * r2 % mn * (mn + 1) % mo1;
    z[k] += C1[0][i], z[(mn + k) % mo1] += C1[1][i];
  }
  for (i = 0; i <= mn2 - 1; i++) {
    k = (long long)i * r1 % mn * (mn + 1) % mo1;
    z[k] += C2[0][i], z[(mn + k) % mo1] += C2[1][i];
  }
  j = 1;
  for (i = 0; i <= mo1 - 1; i++)
    ans += (z[i] % mo) * j % mo, j = (long long)j * c % mo;
  printf("%lld\n", ans % mo);
}