CF645F.Cowslip Collections

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__i 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__j 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 109 + 7.

为了与捣蛋制造者（Mischievous Mess Makers）达成和解，贝茜（Bessie）与农夫约翰（Farmer John）计划种植若干花圃，以搭配波维尼亚（Bovinia）郁郁葱葱的草地。正如任何一位优秀的园艺师所知，他们所种植的每个花圃必须具有完全相同的花卉布局。最初，农夫约翰拥有 $n$ 种不同的花卉可供种植，其中第 $i$ 种花卉有 $a_i$ 朵。

接下来的 $q$ 天中，每天农夫约翰都会收到一批新品种的花卉。在第 $j$ 天，他将收到 $c_j$ 朵同一种类的花卉，且该种类与农夫约翰目前已有的所有花卉种类均不相同。

农夫约翰深谙奢华与极简主义之间的平衡之道，因此希望恰好使用 $k$ 种花卉。此外，为减少浪费，他所选定的这 $k$ 种花卉中的每一朵花都必须被种入某个花圃中；同时，所有花圃必须完全相同——即：所选的 $k$ 种花卉在每个花圃中各自出现的数量必须相等。由于农夫约翰是“国家平等”（national equality）的坚定拥护者，他希望尽可能多地创建花圃。

在每一天（共 $q$ 天）收到花卉后，农夫约翰希望知道：对所有可能的 $k$ 种花卉的选择方案，其各自所能创建的最大花圃数目之和。由于该结果可能非常大，请你输出其对 $10^9 + 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__i (1 ≤ a__i ≤ 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__j (1 ≤ c__j ≤ 1 000 000), the number of flowers of a new species Farmer John receives on day j.

输入的第一行包含三个整数 $n$、$k$ 和 $q$（$1 \leq k \leq n \leq 100\,000$，$1 \leq q \leq 100\,000$）。

接下来的 $n$ 行中，第 $i$ 行（$1 \leq i \leq n$）包含一个整数 $a_i$（$1 \leq a_i \leq 1\,000\,000$），表示农夫约翰最初拥有的第 $i$ 种花的数量。

再接下来的 $q$ 行中，第 $j$ 行（$1 \leq j \leq q$）包含一个整数 $c_j$（$1 \leq c_j \leq 1\,000\,000$），表示农夫约翰在第 $j$ 天收到的一种新花种的花朵数量。

After each of the q days, output the sum of the maximum possible number of gardens, where the sum is taken over all possible choices of k species, modulo 109 + 7.

在每一天操作结束后，输出所有可能的 $k$ 种物种选择方案下、花园最大可能数量的总和（对 $10^9 + 7$ 取模）。

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.

在第一个样例中，第一天结束后，约翰农民每种花的数量分别为 $(4,\,6,\,9,\,8)$，且 $k = 3$。

选择 $(4,\,6,\,8)$ 可使他建造 $2$ 座花园，每座花园中各类花的数量分别为 $(2,\,3,\,4)$；而选择 $(4,\,6,\,9)$、$(4,\,9,\,8)$ 和 $(6,\,9,\,8)$ 各自仅能建造 $1$ 座花园，因为不存在一个花园数量，使得每种花的数量均能被其整除。因此，对所有 $k = 3$ 种花的组合求和，结果为 $2 + 1 + 1 + 1 = 5$。

第二天结束后，约翰农民每种花的数量分别为 $(4,\,6,\,9,\,8,\,6)$。对所有组合求和的结果为 $1 + 2 + 2 + 1 + 1 + 2 + 2 + 3 + 1 + 1 = 16$。

在第二个样例中，$k = 1$。当有 $x$ 朵花时，约翰农民可建造 $x$ 座花园。因此，两个查询的答案分别为 $6 + 5 + 4 + 3 + 2 = 20$ 和 $6 + 5 + 4 + 3 + 2 + 1 = 21$。