Задача №115383. Бесконечная зима в Карелии
Студенты одного из столичных вузов приехали на сборы в Карелию, где каждый день не только пишут тренировки, но и посещают местные музеи. С недавних пор страна перешла на денежные купюры с различными номиналами \(a_1, a_2, \ldots, a_k\) рублей.
При этом номиналы купюр таковы, что каждое из чисел \(a_1, \ldots, a_k\) является делителем числа \(d\). Друзья хотят посетить \(q\) музеев, при этом вход в \(i\)-й из них стоит \(x_i\) рублей. Для каждого из музеев студенты хотят определить, сколько существует способов набрать сумму \(x_i\), используя доступные купюры.
Два способа набрать сумму \(x\) считаются различными, если хотя бы для одного \(j\) (\(1 \le j \le k\)) количество взятых купюр вида \(j\) в этих способах отличается.
Так как ответ на задачу может оказаться слишком большим, выведите его по модулю \(10^9+7\).
Первая строка содержит три целых числа \(d\), \(k\) и \(q\) (\(1 \le d, k, q \le 15\,000\)) — общее кратное всех номиналов, количество различных купюр и количество музеев, которые хотят посетить студенты.
Вторая строка содержит \(k\) различных целых чисел \(a_1, a_2, \ldots, a_k\) (\(1 \le a_1 < a_2 < \ldots < a_k \le d\), \(d\) делится на каждое из \(a_i\)) — номиналы купюр, которые теперь используются в стране.
Третья строка содержит \(q\) целых чисел \(x_1, x_2, \ldots, x_q\) (\(1 \le x_i \le 10^{18}\)) — стоимости билетов.
Выведите \(q\) целых чисел — ответы на задачу для каждого из соответствующих запросов.
Тесты к этой задаче состоят из примеров и \(9\) групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.
| Доп. ограничения | |||||||
| Группа | Баллы | \(d\) | \(k\) | \(q\) | \(x_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | – | Тесты из условия. |
| 1 | 7 | – | \(k=2\) | \(q \le 40\) | \(x_i \le 15\,000\) | – | – |
| 2 | 4 | – | \(k=2\) | \(q \le 40\) | \(x_i \le 10^9\) | \(1\) | – |
| 3 | 11 | \(d \le 10\) | – | \(q \le 40\) | \(x_i \le 40\) | – | – |
| 4 | 23 | \(d \le 20\) | – | \(q \le 40\) | \(x_i \le 10^5\) | \(3\) | – |
| 5 | 12 | \(d \le 20\) | – | \(q \le 100\) | – | 3 – 4 | – |
| 6 | 11 | \(d \le 512\) | – | \(q \le 100\) | – | – | \(d = 2^{k-1}\) |
| 7 | 13 | \(d \le 512\) | – | \(q \le 100\) | – | 6 | \(d\) — степень двойки |
| 8 | 13 | \(d \le 1000\) | – | \(q \le 1000\) | – | 3 – 7 | – |
| 9 | 6 | – | – | – | – | 0 – 8 | – |
В первом примере есть \(2\) способа набрать сумму \(3\): \(1 + 1 + 1\) и \(1 + 2\).
Во втором примере невозможно набрать сумму \(3\), используя только номиналы \(2\) и \(5\). При этом есть \(2\) способа набрать сумму \(10\): \(2 + 2 + 2 + 2 + 2\) и \(5 + 5\).
10 3 5 1 2 5 3 10 22 42 99
2 10 34 106 530
10 2 5 2 5 3 10 22 99 42
0 2 3 10 5
8 4 1 1 2 4 8 1000000000000000000
585937984