F. Ароматные эксперименты
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы отпраздновать установление мира, Бесси, Элси и Фермер Джон собираются посадить несколько грядок с цветами, что позволит им дополнительно украсить роскошные луга Бовинии. Как известно любому садоводу, на каждой грядке необходимо посадить одинаковые цветы в одинаковом порядке. Изначально у Фермера Джона есть n различных типов цветов, ai цветов типа i.

В каждый из q последующих дней Фермер Джон получит некоторое количество цветов нового типа. В день j он получит cj цветов одного типа, отличного от всех типов, имевшихся у него до этого.

Поскольку Фермер Джон знает баланс между экстравагантностью и минимализмом, он хочет посадить цветы ровно k различных типов. Кроме того, если какой-то тип был выбран для использования, то Джон хочет посадить все цветы этого типа. Дополнительно: цветы будут посажены на несколько грядок таким образом, что для каждого из k выбранных типов, количество цветов этого типа на каждой грядке одинаково. Поскольку Джон — фанат всеобщего равенства, он хочет, чтобы количество грядок при этом было максимально.

Для каждого из q дней Фермер Джон хотел бы знать сумму по всем возможным способам выбрать k типов, максимального количества грядок, которое он может сделать для этого подмножества типов. Поскольку это число может быть достаточно большим, выведите его по модулю 109 + 7.

Входные данные

В первой строке входных данных записаны три целых числа n, k и q (1 ≤ k ≤ n ≤ 100 000, 1 ≤ q ≤ 100 000).

В i-й из следующих n строк записано число ai (1 ≤ ai ≤ 1 000 000) — количество цветов типа i, изначально имеющееся у Фермера Джона.

В j-й из следующих q строк записано число cj (1 ≤ cj ≤ 1 000 000) — количество цветов нового типа, которые Фермер Джон получает в день j.

Выходные данные

Для каждого из q дней выведите сумму максимально возможного количества грядок по всем способам выбрать ровно k типов цветов. Ответ выводите по модулю 109 + 7.

Примеры
Входные данные
3 3 2
4
6
9
8
6
Выходные данные
5
16
Входные данные
4 1 2
6
5
4
3
2
1
Выходные данные
20
21
Примечание

В первом примере k = 3. После первого дня у Фермера Джона есть (4, 6, 9, 8) цветов разных типов.

Если выбрать (4, 6, 8), то можно разбить их на 2 грядки по 2, 3, 4 цветка соответствующего типа на каждой.

Если выбрать (4, 6, 9), (4, 9, 8) или (6, 9, 8), то можно будет сделать только одну грядку. Таким образом, сумма по всем подмножествам размера 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 для второго.