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;
struct Complex {
  double x, y;
  Complex() {}
  Complex(double a, double b) : x(a), y(b) {}
  Complex operator+(Complex b) { return Complex(x + b.x, y + b.y); }
  Complex operator-(Complex b) { return Complex(x - b.x, y - b.y); }
  Complex operator*(Complex b) {
    return Complex(x * b.x - y * b.y, x * b.y + y * b.x);
  }
};
const double PI = acos(-1.0);
const int Maxn = 1 << 10;
Complex *w[10];
void fft_init() {
  for (int i = 2, t = 0; i <= Maxn; i <<= 1, t++) {
    w[t] = new Complex[i >> 1];
    for (int j = 0; j < (i >> 1); j++)
      w[t][j] = Complex(cos(2.0 * PI * j / i), sin(2.0 * PI * j / i));
  }
}
void rev(Complex *p, int len) {
  int j = len >> 1;
  for (int i = 1; i < len - 1; i++) {
    if (i < j) swap(p[i], p[j]);
    int k = len >> 1;
    while (j >= k) {
      j -= k;
      k >>= 1;
    }
    if (j < k) j += k;
  }
}
void fft(Complex *p, int len, int check) {
  rev(p, len);
  for (int i = 2, t = 0; i <= len; i <<= 1, t++)
    for (int j = 0; j < len; j += i)
      for (int k = j; k < j + (i >> 1); k++) {
        Complex u = p[k];
        Complex v = w[t][k - j] * p[k + (i >> 1)];
        p[k] = u + v;
        p[k + (i >> 1)] = u - v;
      }
  if (check == -1) {
    reverse(p + 1, p + len);
    for (int i = 0; i < len; i++) {
      p[i].x /= len;
      p[i].y /= len;
    }
  }
}
void fwt(Complex p[][1 << 10][1 << 10], int check) {
  static Complex t1[Maxn];
  for (int i = 0; i < (1 << 10); i++)
    for (int j = 0; j < (1 << 10); j++)
      p[0][i][j] = p[0][i][j] + Complex(check, 0) * p[1][i][j];
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < (1 << 10); j++) {
      for (int k = 0; k < (1 << 10); k++) t1[k] = p[i][j][k];
      fft(t1, 1 << 10, check);
      for (int k = 0; k < (1 << 10); k++) p[i][j][k] = t1[k];
    }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < (1 << 10); j++) {
      for (int k = 0; k < (1 << 10); k++) t1[k] = p[i][k][j];
      fft(t1, 1 << 10, check);
      for (int k = 0; k < (1 << 10); k++) p[i][k][j] = t1[k];
    }
}
int mi1[491], id1[491];
int mi2[499], id2[499];
int id[2][491][499];
void pre(int d) {
  int s = 1;
  for (int i = 0; i < 490; i++) {
    mi1[i] = s;
    id1[s] = i;
    s = s * 2 % 491;
  }
  s = 1;
  for (int i = 0; i < 498; i++) {
    mi2[i] = s;
    id2[s] = i;
    s = s * 7 % 499;
  }
  s = 1;
  for (int i = 0; i < 490019 - 1; i++) {
    id[i % 2][i % 491][i % 499] = s;
    s = (long long)s * d % 490019;
  }
}
Complex p[2][1 << 10][1 << 10], q[2][1 << 10][1 << 10];
int a[2][491][499], b[2][491][499];
int main() {
  fft_init();
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  pre(k);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    int s = (long long)i * i % (490019 - 1);
    a[s % 2][s % 491][s % 499] = (a[s % 2][s % 491][s % 499] + x) % 490019;
  }
  for (int i = 0; i < m; i++) {
    int x;
    scanf("%d", &x);
    int s = (long long)i * i % (490019 - 1) * i % (490019 - 1);
    b[s % 2][s % 491][s % 499] = (b[s % 2][s % 491][s % 499] + x) % 490019;
  }
  for (int i = 0; i < 2; i++)
    for (int j = 1; j < 491; j++)
      for (int k = 1; k < 499; k++) {
        p[i][id1[j]][id2[k]] = Complex(a[i][j][k], 0);
        q[i][id1[j]][id2[k]] = Complex(b[i][j][k], 0);
      }
  fwt(p, 1);
  fwt(q, 1);
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < (1 << 10); j++)
      for (int k = 0; k < (1 << 10); k++) p[i][j][k] = p[i][j][k] * q[i][j][k];
  fwt(p, -1);
  int ans = 0;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < (1 << 10); j++)
      for (int k = 0; k < (1 << 10); k++) {
        long long val = (long long)(p[i][j][k].x + 0.5) % 490019;
        if (!val) continue;
        ans = (ans + val * id[i % 2][mi1[j % 490]][mi2[k % 498]]) % 490019;
      }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 491; j++)
      for (int k = 0; k < 499; k++)
        if ((!j || !k) && a[i][j][k]) {
          long long x = a[i][j][k];
          for (int t1 = 0; t1 < 2; t1++)
            for (int t2 = 0; t2 < 491; t2++)
              for (int t3 = 0; t3 < 499; t3++)
                if (b[t1][t2][t3])
                  ans = (ans + x * b[t1][t2][t3] % 490019 *
                                   id[i * t1 % 2][j * t2 % 491][k * t3 % 499]) %
                        490019;
        }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 491; j++)
      for (int k = 0; k < 499; k++)
        if ((!j || !k) && b[i][j][k]) {
          long long x = b[i][j][k];
          for (int t1 = 0; t1 < 2; t1++)
            for (int t2 = 0; t2 < 491; t2++)
              for (int t3 = 0; t3 < 499; t3++)
                if (t2 && t3 && a[t1][t2][t3])
                  ans = (ans + x * a[t1][t2][t3] % 490019 *
                                   id[i * t1 % 2][j * t2 % 491][k * t3 % 499]) %
                        490019;
        }
  printf("%d\n", ans);
  return 0;
}