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>
namespace IO {
char ibuf[(1 << 21) + 1], *iS, *iT;
char Get() {
  return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, (1 << 21) + 1, stdin),
                      (iS == iT ? EOF : *iS++))
                   : *iS++);
}
int read() {
  int x = 0, c = Get();
  while (!isdigit(c)) c = Get();
  while (isdigit(c)) x = x * 10 + c - 48, c = Get();
  return x;
}
}  // namespace IO
using IO::read;
using ld = double;
const ld pi = 2 * acos(-1);
const int P = 490019, pa = 491, pb = 499, ga = 2, gb = 7, N = 100007, M = 1025;
void inc(int& a, int b) { a += b - P, a += a >> 31 & P; }
void dec(int& a, int b) { a -= b, a += a >> 31 & P; }
int mul(int a, int b) { return 1ll * a * b % P; }
int pow(int a, int k) {
  int r = 1;
  for (; k; k >>= 1, a = mul(a, a))
    if (k & 1) r = mul(a, r);
  return r;
}
struct complex {
  ld x, y;
  complex(ld a = 0, ld b = 0) { x = a, y = b; }
} w[N], A[2][M][M], B[2][M][M], a[M], b[M];
complex operator+(complex a, complex b) { return {a.x + b.x, a.y + b.y}; }
complex operator-(complex a, complex b) { return {a.x - b.x, a.y - b.y}; }
complex operator/(complex a, ld x) { return {a.x / x, a.y / x}; }
complex operator*(complex a, complex b) {
  return {a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x};
}
void operator-=(complex& a, complex b) { a = a - b; }
void operator+=(complex& a, complex b) { a = a + b; }
int lim = 1024, rev[M], sa[P], sb[P], ia[pa], ib[pb], s[P], p[2][M][M];
std::vector<int> vec;
void init() {
  static ld x;
  for (int i = 1; i < lim; ++i) rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? 512 : 0);
  for (int i = 0; i < 512; ++i) x = pi * i / lim, w[512 + i] = {cos(x), sin(x)};
  for (int i = 511; i; --i) w[i] = w[i << 1];
}
void FFT(complex* a, int f) {
  static complex x;
  if (!~f) std::reverse(a + 1, a + lim);
  for (int i = 0; i < lim; ++i)
    if (i < rev[i]) std::swap(a[i], a[rev[i]]);
  for (int i = 1; i < lim; i <<= 1)
    for (int j = 0, d = i << 1; j < lim; j += d)
      for (int k = 0; k < i; ++k)
        x = a[i + j + k] * w[i + k], a[i + j + k] = a[j + k] - x, a[j + k] += x;
  if (!~f)
    for (int i = 0; i < lim; ++i) a[i] = a[i] / lim;
}
int main() {
  int n = read(), m = read(), c = read(), ans = 0;
  init();
  for (int i = 0; i < n; ++i) inc(sa[1ll * i * i % (P - 1)], read());
  for (int i = 0; i < m; ++i) inc(sb[1ll * i * i * i % (P - 1)], read());
  for (int i = 0; i < P - 1; ++i)
    if (!(i % pa) || !(i % pb)) vec.push_back(i);
  for (int i = 0; i < P - 1; ++i)
    if (sb[i])
      for (int j : vec)
        if (sa[j]) inc(s[1ll * i * j % (P - 1)], mul(sb[i], sa[j]));
  for (int i = 0; i < P - 1; ++i)
    if (sa[i] && i % pa && i % pb)
      for (int j : vec)
        if (sb[j]) inc(s[1ll * i * j % (P - 1)], mul(sa[i], sb[j]));
  for (int i = 0, x = 1; i < pa - 1; ++i) ia[x] = i, x = x * ga % pa;
  for (int i = 0, x = 1; i < pb - 1; ++i) ib[x] = i, x = x * gb % pb;
  for (int i = 0; i < P; ++i)
    if (i % pa && i % pb) {
      int x = i % 2, y = ia[i % pa], z = ib[i % pb];
      A[x][y][z] = sa[i], B[x][y][z] = sb[i], p[x][y][z] = i;
    }
  for (int i = 0; i < pa; ++i)
    for (int j = 0; j < pb; ++j)
      A[0][i][j] += A[1][i][j], B[0][i][j] += B[1][i][j];
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < pa; ++j) FFT(A[i][j], 1), FFT(B[i][j], 1);
  for (int i = 0; i < 2; ++i)
    for (int k = 0; k < lim; ++k) {
      for (int j = 0; j < lim; ++j) a[j] = A[i][j][k], b[j] = B[i][j][k];
      FFT(a, 1), FFT(b, 1);
      for (int j = 0; j < lim; ++j) a[j] = a[j] * b[j];
      FFT(a, -1);
      for (int j = 0; j < lim; ++j) A[i][j][k] = a[j];
    }
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < lim; ++j) FFT(A[i][j], -1);
  for (int i = 0; i < lim; ++i)
    for (int j = 0; j < lim; ++j) A[0][i][j] -= A[1][i][j];
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < lim; ++j)
      for (int k = 0; k < lim; ++k)
        inc(s[p[i][j % (pa - 1)][k % (pb - 1)]],
            (long long)(A[i][j][k].x + 0.5) % P);
  for (int i = 0, x = 1; i < P; ++i) inc(ans, mul(x, s[i])), x = mul(x, c);
  printf("%d", ans);
}