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;
template <typename T>
bool chmin(T &a, const T &b) {
  return a > b ? a = b, true : false;
}
template <typename T>
bool chmax(T &a, const T &b) {
  return a < b ? a = b, true : false;
}
template <typename A, typename B>
ostream &operator<<(ostream &out, const pair<A, B> &p) {
  return out << '(' << p.first << ", " << p.second << ')';
}
template <const int P = 998244353, const int g = 3, int maxN = (1 << 20)>
struct FNT {
  int n;
  int rev[maxN];
  int p[maxN], ip[maxN];
  FNT() : n(0) {}
  long long qpow(long long a, long long b) {
    long long r = 1;
    while (b) {
      if (b & 1) (r *= a) %= P;
      (a *= a) %= P;
      b >>= 1;
    }
    return r;
  }
  void prepare(int n) {
    this->n = n;
    assert((n & (n - 1)) == 0);
    int width = 0;
    while ((1 << width) < n) ++width;
    rev[0] = 0;
    for (int i = 1; i < n; ++i)
      rev[i] = rev[i >> 1] >> 1 | (i & 1) << (width - 1);
    p[0] = 1;
    p[1] = qpow(g, (P - 1) / n);
    ip[0] = 1;
    ip[1] = qpow(p[1], P - 2);
    for (int i = 2; i < n; ++i)
      p[i] = (long long)p[i - 1] * p[1] % P,
      ip[i] = (long long)ip[i - 1] * ip[1] % P;
  }
  void transform(vector<int> &a, int flag) {
    int n = a.size();
    if (this->n != n) prepare(n);
    assert(flag == 1 || flag == -1);
    for (int i = 0; i < n; ++i)
      if (rev[i] < i) std::swap(a[i], a[rev[i]]);
    for (int i = 1; i < n; i <<= 1) {
      int step = n / (i << 1);
      for (int j = 0; j < n; j += (i << 1)) {
        int *w = flag == 1 ? p : ip;
        for (int k = 0; k < i; ++k, w += step) {
          int x = a[j + k], y = (long long)a[j + k + i] * *w % P;
          a[j + k] = x + y >= P ? x + y - P : x + y;
          a[j + k + i] = x - y < 0 ? x - y + P : x - y;
        }
      }
    }
    if (flag == -1) {
      long long in = qpow(n, P - 2);
      for (int i = 0; i < n; ++i) a[i] = a[i] * in % P;
    }
  }
};
template <const long long P>
long long qpow(long long a, long long b) {
  long long r = 1;
  while (b) {
    if (b & 1) (r *= a) %= P;
    (a *= a) %= P;
    b >>= 1;
  }
  return r;
}
const long long P1 = 998244353, P2 = 1004535809;
const long long I1 = qpow<P2>(P1, P2 - 2), I2 = qpow<P1>(P2, P1 - 2);
FNT<P1, 3, 1 << 20> f1;
FNT<P2, 3, 1 << 20> f2;
long long mul(long long x, long long y, long long M) {
  using ULL = unsigned long long;
  long long a = (ULL)x * (ULL)y, b = (ULL)((long double)x / M * y) * (ULL)M;
  if (a - b < (1ull << 63))
    return (a - b) % M;
  else
    return (M - (b - a) % M) % M;
}
const int P = 490019;
const int maxN = (1 << 20) + 5;
int n, m, a[maxN], b[maxN], c, f[maxN], g[maxN];
long long p[maxN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  scanf("%d %d %d", &n, &m, &c);
  for (int i = 0; i < n; ++i) scanf("%d", a + i);
  for (int i = 0; i < m; ++i) scanf("%d", b + i);
  p[0] = 1;
  for (int i = 1; i < (1 << 20); ++i) p[i] = p[i - 1] * c % P;
  memset(f, 0, sizeof(f));
  memset(g, 0, sizeof(g));
  for (int i = 0; i < n; ++i) (f[(long long)i * i % (P - 1)] += a[i]) %= P;
  for (int i = 0; i < m; ++i) (g[(long long)i * i * i % (P - 1)] += b[i]) %= P;
  for (int i = 0; i < P; ++i)
    f[i] = f[i] * p[P - 1 - (long long)i * (i + 1) / 2 % (P - 1)] % P;
  for (int i = 0; i < P; ++i)
    g[i] = g[i] * p[P - 1 - (long long)i * (i + 1) / 2 % (P - 1)] % P;
  vector<int> a, b;
  a.assign(f, f + (1 << 20));
  b.assign(g, g + (1 << 20));
  f1.transform(a, 1);
  f1.transform(b, 1);
  vector<int> c1(1 << 20);
  for (int i = 0; i < (1 << 20); ++i) c1[i] = (long long)a[i] * b[i] % P1;
  f1.transform(c1, -1);
  a.assign(f, f + (1 << 20));
  b.assign(g, g + (1 << 20));
  f2.transform(a, 1);
  f2.transform(b, 1);
  vector<int> c2(1 << 20);
  for (int i = 0; i < (1 << 20); ++i) c2[i] = (long long)a[i] * b[i] % P2;
  f2.transform(c2, -1);
  vector<int> r(1 << 20);
  for (int i = 0; i < (1 << 20); ++i)
    r[i] = (mul(c1[i], I2 * P2, P1 * P2) + mul(c2[i], I1 * P1, P1 * P2)) %
           (P1 * P2) % P;
  long long ans = 0;
  for (int i = 0; i < (1 << 20); ++i)
    (ans += (long long)r[i] * p[(long long)i * (i + 1) / 2 % (P - 1)]) %= P;
  cout << ans << endl;
  return 0;
}