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>
const int mod = 490019;
const int phi = mod - 1;
const int MAXN = 1 << 20 | 1;
const int mod1 = 998244353;
const int mod2 = 1004535809;
int pow(int a, int b, int m, int r = 1) {
  for (; b; b >>= 1, a = (long long)a * a % m)
    if (b & 1) r = (long long)r * a % m;
  return r;
}
const int imod = pow(mod1, mod2 - 2, mod2);
class num {
  int a1, a2;

 public:
  num() { a1 = a2 = 0; }
  num(int x) { a1 = x, a2 = x; }
  num(int a, int b) { a1 = a, a2 = b; }
  num operator+(num b) const {
    b.a1 += a1 - mod1;
    b.a1 += b.a1 >> 31 & mod1;
    b.a2 += a2 - mod2;
    b.a2 += b.a2 >> 31 & mod2;
    return b;
  }
  num operator-(num b) const {
    num r = *this;
    r.a1 -= b.a1;
    r.a1 += r.a1 >> 31 & mod1;
    r.a2 -= b.a2;
    r.a2 += r.a2 >> 31 & mod2;
    return r;
  }
  num operator*(num b) const {
    b.a1 = (long long)a1 * b.a1 % mod1;
    b.a2 = (long long)a2 * b.a2 % mod2;
    return b;
  }
  num pow(int x, int y) const {
    return num(::pow(a1, x, mod1), ::pow(a2, y, mod2));
  }
  num inv() const { return pow(mod1 - 2, mod2 - 2); }
  long long operator()() const {
    int k = (long long)(a2 - a1 + mod2) * imod % mod2;
    return (long long)k * mod1 + a1;
  }
} wn[MAXN], wt[MAXN];
int rev[MAXN], lim, dig;
void init(int sz) {
  lim = 1, dig = -1;
  while (lim < sz) lim <<= 1, ++dig;
  for (int i = 0; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << dig;
  const num Wn = num(3).pow((mod1 - 1) / lim, (mod2 - 1) / lim);
  *wn = num(1);
  for (int i = 1; i <= lim; ++i) wn[i] = wn[i - 1] * Wn;
}
void NTT(num* A, int typ) {
  for (int i = 0; i < lim; ++i)
    if (i < rev[i]) std::swap(A[i], A[rev[i]]);
  for (int mid = 1; mid != lim; mid <<= 1) {
    const int Wn = lim / mid / 2;
    for (int i = 0, W = 0; i != mid; ++i, W += Wn)
      wt[i] = wn[typ == 1 ? W : lim - W];
    for (int k = 0; k != lim; k += mid << 1) {
      const num* W = wt;
      for (int l = 0; l != mid; ++l) {
        num X = A[l + k], Y = *(W++) * A[l + k + mid];
        A[l + k] = X + Y;
        A[l + k + mid] = X - Y;
      }
    }
  }
  if (typ == -1) {
    num liminv = num(lim).inv();
    for (int i = 0; i != lim; ++i) A[i] = A[i] * liminv;
  }
}
int pw[mod], ipw[mod];
int n, m, C;
int A[MAXN], B[MAXN];
int comb(int x) { return (long long)x * (x - 1) / 2 % phi; }
int main() {
  std::ios_base::sync_with_stdio(false), std::cin.tie(0);
  std::cin >> n >> m >> C;
  int IC = -1;
  for (int i = 1; i < mod; ++i)
    if ((long long)C * i % mod == 1) {
      IC = i;
      break;
    }
  for (int i = *pw = *ipw = 1; i != mod; ++i) {
    pw[i] = (long long)pw[i - 1] * C % mod;
    ipw[i] = (long long)ipw[i - 1] * IC % mod;
  }
  for (int i = 0, t, v; i < n; ++i) {
    std::cin >> v, t = (long long)i * i % phi;
    A[t] = (A[t] + (long long)v * ipw[comb(t)]) % mod;
  }
  for (int i = 0, t, v; i < m; ++i) {
    std::cin >> v, t = (long long)i * i * i % phi;
    B[t] = (B[t] + (long long)v * ipw[comb(t)]) % mod;
  }
  static num ta[MAXN], tb[MAXN];
  const int sz = phi + phi - 1;
  init(sz);
  for (int i = 0; i < phi; ++i) ta[i] = num(A[i]);
  for (int i = 0; i < phi; ++i) tb[i] = num(B[i]);
  NTT(ta, 1);
  NTT(tb, 1);
  for (int i = 0; i < lim; ++i) ta[i] = ta[i] * tb[i];
  NTT(ta, -1);
  int ans = 0;
  for (int i = 0; i < sz; ++i)
    ans = (ans + (long long)ta[i]() % mod * pw[comb(i)]) % mod;
  std::cout << ans << std::endl;
  return 0;
}