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 x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
  return x * f;
}
const int lim = (1 << 20);
const int mod = 490019;
const int phi = mod - 1;
const double pi = acos(-1);
int qpow(int x, int y = mod - 2, int p = mod) {
  int res = 1;
  for (; y; x = 1ll * x * x % p, y >>= 1)
    if (y & 1) res = 1ll * res * x % p;
  return res;
}
struct CP {
  double x, y;
  CP(double xx = 0, double yy = 0) { x = xx, y = yy; }
};
CP operator+(CP aa, CP bb) { return CP(aa.x + bb.x, aa.y + bb.y); }
CP operator-(CP aa, CP bb) { return CP(aa.x - bb.x, aa.y - bb.y); }
CP operator*(CP aa, CP bb) {
  return CP(aa.x * bb.x - aa.y * bb.y, aa.x * bb.y + aa.y * bb.x);
}
int pp[lim];
void NTT(CP *f, int flag) {
  for (int i = 0, iE = lim - 1; i <= iE; i++)
    if (pp[i] < i) swap(f[i], f[pp[i]]);
  for (int i = 2; i <= lim; i <<= 1) {
    CP ch(cos(2 * pi / i), flag * sin(2 * pi / i));
    for (int j = 0, l = (i >> 1); j < lim; j += i) {
      CP now(1, 0);
      for (int k = j; k < j + l; k++) {
        CP pa = f[k], pb = f[k + l] * now;
        f[k] = pa + pb, f[k + l] = pa - pb, now = now * ch;
      }
    }
  }
  if (flag == -1)
    for (int i = 0, iE = lim - 1; i <= iE; i++) f[i].x /= lim, f[i].y /= lim;
}
CP Aa[lim], Ab[lim], Ba[lim], Bb[lim], Sa[lim], Sb[lim], Sc[lim];
int n, m, c, f[lim], pA[lim], pB[lim], ans[lim], Pow[lim], iPow[lim], ic, Ans;
int main() {
  n = read(), m = read(), c = read();
  ic = qpow(c), Pow[0] = iPow[0] = 1;
  for (int i = 1, iE = phi; i <= iE; i++)
    Pow[i] = 1ll * Pow[i - 1] * c % mod, iPow[i] = 1ll * iPow[i - 1] * ic % mod;
  for (int i = 0, iE = n - 1; i <= iE; i++)
    (pA[(long long)i * i % phi] += read()) %= mod;
  for (int i = 0, iE = m - 1; i <= iE; i++)
    (pB[(long long)i * i % phi * i % phi] += read()) %= mod;
  for (int i = 0, iE = lim - 1; i <= iE; i++)
    pA[i] = 1ll * pA[i] * iPow[(long long)i * (i - 1) / 2 % phi] % mod;
  for (int i = 0, iE = lim - 1; i <= iE; i++)
    pB[i] = 1ll * pB[i] * iPow[(long long)i * (i - 1) / 2 % phi] % mod;
  for (int i = 0, iE = lim - 1; i <= iE; i++)
    pp[i] = ((pp[i >> 1] >> 1) | ((i & 1) * (lim >> 1)));
  for (int i = 0, iE = lim - 1; i <= iE; i++)
    Aa[i].x = (pA[i] & 1023), Ab[i].x = (pA[i] >> 10), Ba[i].x = (pB[i] & 1023),
    Bb[i].x = (pB[i] >> 10);
  NTT(Aa, 1), NTT(Ab, 1), NTT(Ba, 1), NTT(Bb, 1);
  for (int i = 0, iE = lim - 1; i <= iE; i++)
    Sa[i] = Aa[i] * Ba[i], Sb[i] = Aa[i] * Bb[i] + Ab[i] * Ba[i],
    Sc[i] = Ab[i] * Bb[i];
  NTT(Sa, -1), NTT(Sb, -1), NTT(Sc, -1);
  for (int i = 0, iE = lim - 1; i <= iE; i++)
    ans[i] = (long long)(Sa[i].x + 0.49) % mod +
             (long long)(Sb[i].x + 0.49) % mod * 1024 % mod +
             (long long)(Sc[i].x + 0.49) % mod * 1048576 % mod;
  for (int i = 0, iE = lim - 1; i <= iE; i++)
    (Ans += 1ll * ans[i] * Pow[(long long)i * (i - 1) / 2 % phi] % mod) %= mod;
  printf("%d\n", Ans);
  return 0;
}