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;
int gi() {
  int res = 0, w = 1;
  char ch = getchar();
  while (ch != '-' && !isdigit(ch)) ch = getchar();
  if (ch == '-') w = -1, ch = getchar();
  while (isdigit(ch)) res = res * 10 + ch - '0', ch = getchar();
  return res * w;
}
struct comp {
  double x, y;
  comp() : x(0), y(0) {}
  comp(const double &x, const double &y) : x(x), y(y) {}
};
inline comp operator+(const comp &a, const comp &b) {
  return comp(a.x + b.x, a.y + b.y);
}
inline comp operator-(const comp &a, const comp &b) {
  return comp(a.x - b.x, a.y - b.y);
}
inline comp operator*(const comp &a, const comp &b) {
  return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline comp conj(const comp &a) { return comp(a.x, -a.y); }
const double PI = acos(-1.0);
const int MAX_N = 1 << 20 | 10, Mod = 490019;
int upd(int x) { return x + (x >> 31 & Mod); }
void Pls(int &x, int y) { x = upd(x + y - Mod); }
int fpow(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = 1ll * res * x % Mod;
    x = 1ll * x * x % Mod, y >>= 1;
  }
  return res;
}
comp omg[MAX_N];
int Limit, rev[MAX_N];
void FFT_prepare(int len) {
  int p = 0;
  for (Limit = 1; Limit <= len; ++p, Limit <<= 1)
    ;
  for (int i = 0; i < Limit; i++)
    rev[i] = rev[i >> 1] >> 1 | ((i & 1) << (p - 1));
  for (int i = 0; i < Limit; i++)
    omg[i] = comp(cos(PI * i / Limit), sin(PI * i / Limit));
}
void FFT(comp *p, int op) {
  for (int i = 0; i < Limit; i++)
    if (i < rev[i]) swap(p[i], p[rev[i]]);
  for (int i = 1; i < Limit; i <<= 1)
    for (int j = 0; j < Limit; j += (i << 1)) {
      for (int k = 0; k < i; k++) {
        comp w = ::omg[Limit / i * k];
        w.y *= op;
        comp x = p[j + k], y = w * p[i + j + k];
        p[j + k] = x + y, p[i + j + k] = x - y;
      }
    }
}
void MTT(int n, int m, int *x, int *y, int *z) {
  FFT_prepare(n + m);
  static comp a[MAX_N], b[MAX_N];
  static comp dfta[MAX_N], dftb[MAX_N], dftc[MAX_N], dftd[MAX_N];
  for (int i = 0; i < Limit; i++) a[i] = comp(x[i] & 32767, x[i] >> 15);
  for (int i = 0; i < Limit; i++) b[i] = comp(y[i] & 32767, y[i] >> 15);
  FFT(a, 1), FFT(b, 1);
  for (int i = 0; i < Limit; i++) {
    int j = (Limit - i) & (Limit - 1);
    static comp da, db, dc, dd;
    da = (a[i] + conj(a[j])) * comp(0.5, 0),
    db = (a[i] - conj(a[j])) * comp(0, -0.5);
    dc = (b[i] + conj(b[j])) * comp(0.5, 0),
    dd = (b[i] - conj(b[j])) * comp(0, -0.5);
    dfta[j] = da * dc, dftb[j] = da * dd;
    dftc[j] = db * dc, dftd[j] = db * dd;
  }
  for (int i = 0; i < Limit; i++) a[i] = dfta[i] + dftb[i] * comp(0, 1);
  for (int i = 0; i < Limit; i++) b[i] = dftc[i] + dftd[i] * comp(0, 1);
  FFT(a, 1), FFT(b, 1);
  for (int i = 0; i < Limit; i++) {
    int da = (long long)(a[i].x / Limit + 0.5) % Mod;
    int db = (long long)(a[i].y / Limit + 0.5) % Mod;
    int dc = (long long)(b[i].x / Limit + 0.5) % Mod;
    int dd = (long long)(b[i].y / Limit + 0.5) % Mod;
    z[i] = (da + ((long long)(db + dc) << 15) + ((long long)dd << 30)) % Mod;
    z[i] = upd(z[i]);
  }
}
int N, M, A[MAX_N], B[MAX_N], C;
int a[MAX_N], b[MAX_N], c[MAX_N];
int main() {
  N = gi(), M = gi(), C = gi();
  for (int i = 0; i < N; i++) A[i] = gi();
  for (int i = 0; i < M; i++) B[i] = gi();
  for (int i = 0; i < N; i++)
    if (A[i]) Pls(c[1ll * i * i % (Mod - 1)], A[i]);
  for (int i = 0; i < M; i++)
    if (B[i]) Pls(a[1ll * i * i * i % (Mod - 1)], B[i]);
  for (int i = 0; i < Mod - 1; i++)
    if (a[i])
      a[i] = 1ll * a[i] * fpow(C, Mod - 1 - 1ll * (i - 1) * i / 2 % (Mod - 1)) %
             Mod;
  for (int i = 0; i < 2 * (Mod - 1); i++)
    b[i] = fpow(C, 1ll * i * (i - 1) / 2 % (Mod - 1));
  reverse(&a[0], &a[Mod - 1]);
  MTT(Mod - 2, Mod - 2, b, a, b);
  int ans = 0;
  for (int i = 0; i < Mod - 1; i++)
    if (c[i])
      ans = (ans + 1ll * fpow(C, Mod - 1 - 1ll * (i - 1) * i / 2 % (Mod - 1)) *
                       b[i + Mod - 2] % Mod * c[i]) %
            Mod;
  printf("%d\n", ans);
  return 0;
}