In an attempt to make peace with the Mischievious Mess Makers, Bessie and Farmer John are planning to plant some flower gardens to complement the lush, grassy fields of Bovinia. As any good horticulturist knows, each garden they plant must have the exact same arrangement of flowers. Initially, Farmer John has *n* different species of flowers he can plant, with *a*<sub class="lower-index">*i*</sub> flowers of the *i*-th species.

On each of the next *q* days, Farmer John will receive a batch of flowers of a new species. On day *j*, he will receive *c*<sub class="lower-index">*j*</sub> flowers of the same species, but of a different species from those Farmer John already has. 

Farmer John, knowing the right balance between extravagance and minimalism, wants exactly *k* species of flowers to be used. Furthermore, to reduce waste, each flower of the *k* species Farmer John chooses must be planted in some garden. And each of the gardens must be identical; that is to say that each of the *k* chosen species should have an equal number of flowers in each garden. As Farmer John is a proponent of national equality, he would like to create the greatest number of gardens possible.

After receiving flowers on each of these *q* days, Farmer John would like to know the sum, over all possible choices of *k* species, of the maximum number of gardens he could create. Since this could be a large number, you should output your result modulo 10<sup class="upper-index">9</sup> + 7.
The first line of the input contains three integers *n*, *k* and *q* (1 ≤ *k* ≤ *n* ≤ 100 000, 1 ≤ *q* ≤ 100 000).

The *i*-th (1 ≤ *i* ≤ *n*) of the next *n* lines of the input contains an integer *a*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 1 000 000), the number of flowers of species *i* Farmer John has initially.

The *j*-th (1 ≤ *j* ≤ *q*) of the next *q* lines of the input contains an integer *c*<sub class="lower-index">*j*</sub> (1 ≤ *c*<sub class="lower-index">*j*</sub> ≤ 1 000 000), the number of flowers of a new species Farmer John receives on day *j*.
In the first sample case, after the first day Farmer John has (4, 6, 9, 8) of each type of flower, and *k* = 3.

Choosing (4, 6, 8) lets him make 2 gardens, each with (2, 3, 4) of each flower, respectively. Choosing (4, 6, 9), (4, 9, 8) and (6, 9, 8) each only let him make one garden, since there is no number of gardens that each species can be evenly split into. So the sum over all choices of *k* = 3 flowers is 2 + 1 + 1 + 1 = 5.

After the second day, Farmer John has (4, 6, 9, 8, 6) of each flower. The sum over all choices is 1 + 2 + 2 + 1 + 1 + 2 + 2 + 3 + 1 + 1 = 16.

In the second sample case, *k* = 1. With *x* flowers Farmer John can make *x* gardens. So the answers to the queries are 6 + 5 + 4 + 3 + 2 = 20 and 6 + 5 + 4 + 3 + 2 + 1 = 21.
3 3 2
4
6
9
8
6
5
16
4 1 2
6
5
4
3
2
1
20
21
3 3 3
6
8
10
12
14
16
8
20
42
1 1 1
1
1
2
10 10 10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
110
660
2860
10010
30030
80080
194480
437580
923780
1847560
7 1 9
3
6
7
2
10
8
1
3
9
2
9
10
2
4
5
2
40
49
51
60
70
72
76
81
83
5 1 7
10
8
4
5
8
3
9
3
9
3
10
1
38
47
50
59
62
72
73
7 2 8
2
5
7
9
6
2
5
2
8
7
10
8
8
5
7
40
52
67
90
113
144
169
195
9 8 10
10
9
6
8
8
8
8
6
2
7
1
9
5
10
8
1
1
6
10
46
166
496
1288
3012
6480
12915
24355
43923
76077
from sys import stdin #Bibliotecas para optimizar la entrada/salida
from sys import stdout

MOD = 1000000007 #Modulo
MAXA = 1000007 #Maximo valor posible en A
MAXN = 200007 #Suma de maximos valores posibles de n y q

p = [0 for i in range(MAXA)]    #Para cada i me guarda 0 si i es primo o 1 en otro caso
phi = [i for i in range(MAXA)]  #Para cada i conserva phi(i)
cant = [0 for _ in range(MAXA)]     #Guarda por cada indice j la cantidad de valores en A_i que son multiplos de j
combin = [0 for _ in range(MAXA)]   #Guarda por cada indice j combinatoria de cant[j] en k

#Computamos la funcion phi para cada numero
def ComputePhi():
    p[0] = 1    # 0 no es primo
    p[1] = 1    # 1 no es primo
    phi[2] = 1  # phi(2) = 1

    for i in range(4,MAXA,2):
        p[i] = 1 #Ningun numero par es primo
        phi[i] = (phi[i]//2)    #Ya que dos es un primo q divide a i

    for i in range(3,MAXA,2):
        if p[i] == 0:
            for j in range(i,MAXA,i):
                if i != j:
                    p[j] = 1
                phi[j] = (phi[j]//i)*(i-1)  #Ya que i es un primo que divide a j

def qp(a,p): #Exponenciacion binaria O(log p)
    a = int(a)
    p = int(p)
    if p == 0:
        return 1
    x = qp(a,p//2)
    x = (x*x)%MOD
    if p%2 == 1:
        x = (x*a)%MOD
    return x

def inv(a): #inverso multiplicativo, ya que el modulo es primo usamos el pequeño teorema de Fermat para hallarlo
    return qp(a,MOD-2)

inputs = list(map(int,stdin.readline().split())) #lee los valores de n,k,q de la entrada
n,k,q= inputs[0],inputs[1],inputs[2]  

fact = [0 for i in range(MAXN)] #Lista que va a mantener para cada valor entre 0 y MAXN el factorial de ese numero (modulado)
ifact = [0 for i in range(MAXN)] #Lista que va a mantener para cada valor entre 0 y MAXN el inverso multiplicativo del factorial de ese numero.


def comb(a,b): #Halla la combinatoria de a en b de acuerdo a la formula
    if a-b < 0:
        return 0
    return ((fact[a]*ifact[b])%MOD*ifact[a-b])%MOD

#Computamos el factorial recursivamente
fact[0] = 1     
for i in range(1,MAXN):
    fact[i] = (fact[i-1]*i)%MOD

#Computamos el inverso multiplicativo del factorial recursivamente teniendo en cuenta que (k!)^(-1) = ((k+1)!^(-1))*(k+1)
ifact[MAXN-1] = inv(fact[MAXN-1])
for i in range(MAXN-2,-1,-1):
    ifact[i] = (ifact[i+1]*(i+1))%MOD

ComputePhi()

#Se leen los valores en A y por cada uno se hallan sus diviores actualizando los valores en (cant)
for j in range(n):
    a = int(stdin.readline())
    for i in range(1,MAXA):
        if i*i > a:
            break
        if a%i == 0:
            cant[a//i]+=1   #a es un multiplo de  a/i
            if i!= a//i:    #Para no agregar el el mismo multiplo dos veces si i*i=a
                cant[i]+=1  #a es multiplo de i 
ans = 0 #Variable donde se calculara la respuesta

for i in range(1,MAXA): #Se actualizan los valores de combin y de ans teniendo en cuenta los elementos de A
    combin[i] = comb(cant[i],k)
    ans += (phi[i]*combin[i])%MOD
    ans%=MOD

#Se leen los q valores y por cada uno se hallan sus diviores y se actualiza la respuesta
for _ in range(q): 
    a = int(stdin.readline())
    for i in range(1,MAXA):
        if i*i > a:
            break
        if a%i == 0:
            #Como cant[a/i] varia hemos de restar este sumando y luego sumar cuando cant[a/i]  este actualizado
            ans -= (phi[a//i] * combin[a//i])%MOD
            ans%=MOD

            if ans < 0: #Si al restar la respuesta se hizo menor que cero añadimos MOD
                ans+=MOD
            
            cant[a//i]+=1
            combin[a//i] = comb(cant[a//i],k)
            ans += (phi[a//i] * combin[a//i])%MOD   #Actualizamos la respuesta de acuerdo al nuevo valor de cant[i]
            ans%=MOD
            
            if i!= a//i:
                #Como cant[i] varia hemos de restar este sumando y luego sumar cuando cant[i] este actualizado
                ans -= (phi[i]*combin[i])%MOD
                ans%=MOD
                if ans < 0: 
                    ans+=MOD
                cant[i]+=1
                combin[i] = comb(cant[i],k)
                ans += (phi[i]*combin[i])%MOD   #Actualizamos la respuesta de acuerdo al nuevo valor de cant[i]
                ans%=MOD

    #Damos finalmente la respuesta
    print(ans)