#include <bits/stdc++.h>   using namespace std;   const int maxn = 1e6 + 10;   const long long mod = 1e9 + 7;   int prime[maxn], g[maxn], last[maxn], num[maxn], cnt[maxn];   long long fac[maxn], invf[maxn];   int t[500];   bool vis[maxn];   long long fpow(long long a, long long b, long long p = mod) {     long long ans = 1;     while (b) {       if (b & 1) ans = ans * a % p;       a = a * a % p;       b >>= 1;     }     return ans;   }   void init() {     int cnt = 0;     g[1] = 1;     last[1] = 1;     fac[1] = 1;     fac[0] = 1;     for (int i = 2; i < maxn; i++) {       fac[i] = fac[i - 1] * i % mod;       if (!vis[i]) prime[++cnt] = i, g[i] = i - 1, last[i] = 1;       for (int j = 1; j <= cnt && i * prime[j] < maxn; j++) {         int x = i * prime[j];         vis[x] = true;         if (i % prime[j] == 0) {           last[x] = last[i];           if (last[x] == 1)             g[x] = x - i;           else             g[x] = g[x / last[x]] * g[last[x]];           break;         }         last[x] = i;         g[x] = g[i] * g[prime[j]];       }     }     invf[maxn - 1] = fpow(fac[maxn - 1], mod - 2);     for (int i = maxn - 2; i >= 0; i--) invf[i] = invf[i + 1] * (i + 1) % mod;   }   long long C(int n, int m) {     return n < m ? 0 : fac[n] * invf[m] % mod * invf[n - m] % mod;   }   int getfac(int x) {     int len = 0;     for (int i = 1; i * i <= x; i++) {       if (x % i) continue;       t[++len] = i;       if (i * i != x) t[++len] = x / i;     }     sort(t + 1, t + 1 + len);     return len;   }   int main() {     std::ios::sync_with_stdio(false);     cout.tie(0);     init();     int n, k, q;     cin >> n >> k >> q;     for (int i = 1; i <= n; i++) {       int x;       cin >> x;       num[x]++;     }     for (int i = maxn - 1; i >= 1; i--) {       for (int j = i; j < maxn; j += i) cnt[i] += num[j];     }     long long ans = 0;     for (int i = 1; i < maxn; i++) {       ans = (ans + C(cnt[i], k) * g[i] % mod) % mod;     }     while (q--) {       int x;       cin >> x;       int len = getfac(x);       for (int i = len; i > 0; i--) {         long long dert = C(cnt[t[i]] + 1, k) - C(cnt[t[i]], k);         dert *= g[t[i]];         ans = (ans + dert + mod) % mod;         cnt[t[i]]++;       }       ans = (ans % mod + mod) % mod;       cout << ans <<   n ;     }     return 0;   }   