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;
const double pi = acos(-1);
namespace FFT {
static const int N = 1024;
int rev[N];
complex<double> w[N];
void FFT_init() {
  rev[0] = 0, rev[1] = N >> 1;
  for (int i = 2; i < N; ++i) rev[i] = rev[i >> 1] >> 1 | rev[i & 1];
  w[0] = complex<double>(1, 0),
  w[1] = complex<double>(cos(2 * pi / N), sin(2 * pi / N));
  for (int i = 2; i < N; ++i) w[i] = w[i - 1] * w[1];
}
void DFT(complex<double> *A) {
  for (int i = 0; i < N; ++i)
    if (i < rev[i]) swap(A[i], A[rev[i]]);
  for (int len = 2; len <= N; len <<= 1) {
    int m = len >> 1;
    for (complex<double> *p = A; p != A + N; p += len)
      for (int i = 0; i < m; ++i) {
        complex<double> u = p[i], v = p[i + m] * w[N / len * i];
        p[i] = u + v;
        p[i + m] = u - v;
      }
  }
}
void IDFT(complex<double> *A) {
  DFT(A);
  reverse(A + 1, A + N);
  for (int i = 0; i < N; ++i) A[i] /= N;
}
complex<double> t[N];
template <void (*T)(complex<double> *)>
void TD(complex<double> A[N][N]) {
  for (int j = 0; j < N; ++j) {
    for (int i = 0; i < N; ++i) t[i] = A[i][j];
    T(t);
    for (int i = 0; i < N; ++i) A[i][j] = t[i];
  }
  for (int i = 0; i < N; ++i) T(A[i]);
}
};  // namespace FFT
using namespace FFT;
const int P1 = 491, P2 = 499;
const int g1 = 2, g2 = 7;
int Log1[P1], Log2[P2];
int n, m, c;
long long a[490019], b[490019];
void init() {
  scanf("%d%d%d", &n, &m, &c);
  for (int x, i = 0; i < n; ++i)
    scanf("%d", &x), (a[(1LL * i * i % (490019 - 1))] =
                          (a[(1LL * i * i % (490019 - 1))] + x) % 490019);
  for (int x, i = 0; i < m; ++i)
    scanf("%d", &x), (b[(1LL * i * i * i % (490019 - 1))] =
                          (b[(1LL * i * i * i % (490019 - 1))] + x) % 490019);
}
bool spc[490019];
vector<int> sp;
int id[2][P1][P2];
complex<double> Ma[2][N][N], Mb[2][N][N], Mc[2][N][N];
long long F[490019];
void predo() {
  for (int x = 1, i = 0; i < P1 - 1; ++i) Log1[x] = i, x = x * g1 % P1;
  for (int x = 1, i = 0; i < P2 - 1; ++i) Log2[x] = i, x = x * g2 % P2;
  for (int i = 0; i < 490019 - 1; ++i) {
    if (i % P1 == 0 || i % P2 == 0)
      spc[i] = 1, sp.push_back(i);
    else {
      int x = Log1[i % P1], y = Log2[i % P2];
      id[i & 1][x][y] = i;
      Ma[i & 1][x][y] += a[i], Mb[i & 1][x][y] += b[i];
    }
  }
  long long cnt = 0;
  for (int i = 0; i < 490019 - 1; ++i)
    if (a[i])
      for (int j : sp)
        if (b[j])
          (F[1LL * i * j % (490019 - 1)] =
               (F[1LL * i * j % (490019 - 1)] + a[i] * b[j]) % 490019);
  for (int j = 0; j < 490019 - 1; ++j)
    if (b[j] && !spc[j])
      for (int i : sp)
        if (a[i])
          (F[1LL * i * j % (490019 - 1)] =
               (F[1LL * i * j % (490019 - 1)] + a[i] * b[j]) % 490019);
}
void solve() {
  for (int i = 0; i < P1 - 1; ++i)
    for (int j = 0; j < P2 - 1; ++j)
      Ma[0][i][j] += Ma[1][i][j], Mb[0][i][j] += Mb[1][i][j];
  for (int c = 0; c <= 1; ++c) {
    TD<DFT>(Ma[c]), TD<DFT>(Mb[c]);
    for (int i = 0; i < N; ++i)
      for (int j = 0; j < N; ++j) Mc[c][i][j] = Ma[c][i][j] * Mb[c][i][j];
    TD<IDFT>(Mc[c]);
  }
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j) Mc[0][i][j] -= Mc[1][i][j];
  for (int c = 0; c <= 1; ++c)
    for (int i = 0; i < N; ++i)
      for (int j = 0; j < N; ++j)
        if (Mc[c][i][j].real() > 1E-5)
          (F[id[c][i % (P1 - 1)][j % (P2 - 1)]] =
               (F[id[c][i % (P1 - 1)][j % (P2 - 1)]] +
                (long long)(Mc[c][i][j].real() + 0.5)) %
               490019);
  long long ans = 0;
  for (int i = 0, pc = 1; i < 490019 - 1; ++i, pc = (long long)pc * c % 490019)
    if (F[i]) (ans = (ans + F[i] * pc) % 490019);
  printf("%lld\n", ans);
}
int main() {
  FFT_init();
  init();
  predo();
  solve();
  return 0;
}