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 int N = 1 << 20;
const double PI = acos(-1);
struct C {
  double x, y;
  inline C operator-(const C& a) const { return (C){x - a.x, y - a.y}; }
  inline C operator+(const C& a) const { return (C){x + a.x, y + a.y}; }
  inline void operator+=(const C& a) {
    x += a.x;
    y += a.y;
  }
  inline C operator*(const double& a) const { return (C){x * a, y * a}; }
  inline C operator/(const double& a) const { return (C){x / a, y / a}; }
  inline C operator*(const C& a) const {
    return (C){x * a.x - y * a.y, x * a.y + y * a.x};
  }
  inline C conj() const { return (C){x, -y}; }
} s1[N], omg_[N], s2[N], s3[N];
int n_, lgn_;
int rev_[N];
void FFT_init(int n) {
  lgn_ = 31 - __builtin_clz(n);
  n_ = 1 << lgn_;
  rev_[0] = 0;
  omg_[0] = (C){1, 0};
  for (int i = 1; i < n_; i <<= 1)
    omg_[i] = (C){cos(2. * i * PI / n_), sin(2. * i * PI / n_)};
  for (int i = 1; i < n_; i++) {
    omg_[i] = omg_[i ^ (i & -i)] * omg_[i & -i];
    rev_[i] = rev_[i / 2] >> 1 | (i & 1) << (lgn_ - 1);
  }
}
C ww[N];
void FFT(C* a) {
  for (int i = 0; i < n_; i++)
    if (rev_[i] < i) swap(a[i], a[rev_[i]]);
  int t;
  for (int i = 0; i < lgn_; i++) {
    t = 1 << i;
    for (int j = 0; j < t; ++j) ww[j] = omg_[j << (lgn_ - i - 1)];
    for (int j = 0; j < n_; j += t << 1) {
      C *at = a + j, *bt = a + j + t;
      for (int k = 0; k < t; ++k) {
        C s = bt[k] * ww[k];
        bt[k] = at[k] - s;
        at[k] += s;
      }
    }
  }
}
void mul(long long* a, long long* b, int n, int m) {
  FFT_init(n + m);
  for (int i = 0; i < n; i++)
    if (i & 1)
      s1[i / 2].y = a[i];
    else
      s1[i / 2].x = a[i];
  for (int i = 0; i < m; i++)
    if (i & 1)
      s2[i / 2].y = b[i];
    else
      s2[i / 2].x = b[i];
  FFT(s1);
  FFT(s2);
  for (int i = 0; i < n_; i++) {
    int j = (n_ - 1) & (n_ - i);
    s3[i] = (s1[i] * s2[i] * (C){4, 0} -
             (s1[i] - s1[j].conj()) * (s2[i] - s2[j].conj()) *
                 (((i & n_ >> 1) ? (C){1, 0} - ww[i ^ n_ >> 1]
                                 : ww[i] + (C){1, 0}))) *
            (C){0.25, 0};
  }
  FFT(s3);
  reverse(s3 + 1, s3 + n_);
  for (int i = 0; i < n + m; i++)
    a[i] = floor(i & 1 ? s3[i >> 1].y / n_ + 0.5 : s3[i >> 1].x / n_ + 0.5);
}
const int mod = 490019, lim = mod - 1;
int n, m, K, ans, pw[N];
long long a[N], b[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> K;
  pw[0] = 1;
  for (int i = 1; i < lim; ++i) pw[i] = (long long)pw[i - 1] * K % mod;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    a[(long long)i * i % lim] += x;
  }
  for (int i = 0; i < m; ++i) {
    int x;
    cin >> x;
    b[(long long)i * i % lim * i % lim] += x;
  }
  for (int i = 0; i < lim; ++i) {
    int t = pw[(lim - (long long)i * (i - 1) / 2 % lim + lim) % lim];
    a[i] = (long long)a[i] * t % mod;
    b[i] = (long long)b[i] * t % mod;
    if (a[i] >= lim / 2) a[i] -= mod;
    if (b[i] > lim / 2) b[i] -= mod;
  }
  mul(a, b, lim, lim);
  for (int i = 0; i < 2 * lim; ++i) {
    a[i] = (a[i] % mod + mod) % mod;
    ans = (ans + (long long)a[i] * pw[(long long)i * (i - 1) / 2 % lim]) % mod;
  }
  cout << ans << '\n';
  return 0;
}