#include <bits/stdc++.h> using namespace std; #define mod 1000000009 #define nmax 1000007 #define fi first #define se second #define ll long long ll t = 1, n, m = 0, i = 0, j = 0, d = 0, x = 0, k = 0, y = 0, z, a[nmax], f[nmax], h[nmax], kq = 0, f1[nmax]; vector<ll> v; ll power(ll n, ll k) { if (k == 0) return 1; ll tam = power(n, k / 2) % mod; if (k % 2 == 0) return (tam * tam) % mod; return (((tam * tam) % mod) * n) % mod; } ll sus(ll n, ll k) { ll tam = f1[k], tam1 = power(f[k], mod - 2) % mod; tam = (tam * tam1) % mod; return tam; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("GCDLCM.INP","r",stdin); // freopen("GCDLCM.OUT","w",stdout); cin >> n >> m >> k; for (i = 2; i <= 1000000; ++i) { for (j = i; j <= 1000000; j += i) { if (!f[j]) f[j] = i; } } for (i = 1; i <= n; ++i) { cin >> x; while (x > 1) { z = f[x]; while (x % z == 0) { x /= z; h[z]--; } } } for (i = 1; i <= m; ++i) { cin >> x; while (x > 1) { z = f[x]; while (x % z == 0) { x /= z; h[z]++; } } } d = 0; z = 1; for (i = 2; i <= 1000000; ++i) { if (h[i] < 0) { cout << 0; return 0; } if (h[i]) { d++; z = (z * h[i]) % mod; v.push_back(h[i]); } } if (k == 1) { if (d == 0) cout << 1; else cout << 0; return 0; } if (k == 2) { cout << power(2, d); return 0; } kq = 1; for (i = 0; i < v.size(); ++i) { x = ((power(v[i] + 1, k) - power(v[i], k) - power(v[i], k) + power(v[i] - 1, k)) % mod + mod) % mod; kq = (kq * x) % mod; } cout << kq; }