Чтобы отпраздновать установление мира, Бесси, Элси и Фермер Джон собираются посадить несколько грядок с цветами, что позволит им дополнительно украсить роскошные луга Бовинии. Как известно любому садоводу, на каждой грядке необходимо посадить одинаковые цветы в одинаковом порядке. Изначально у Фермера Джона есть n различных типов цветов, ai цветов типа i.
В каждый из q последующих дней Фермер Джон получит некоторое количество цветов нового типа. В день j он получит cj цветов одного типа, отличного от всех типов, имевшихся у него до этого.
Поскольку Фермер Джон знает баланс между экстравагантностью и минимализмом, он хочет посадить цветы ровно k различных типов. Кроме того, если какой-то тип был выбран для использования, то Джон хочет посадить все цветы этого типа. Дополнительно: цветы будут посажены на несколько грядок таким образом, что для каждого из k выбранных типов, количество цветов этого типа на каждой грядке одинаково. Поскольку Джон — фанат всеобщего равенства, он хочет, чтобы количество грядок при этом было максимально.
Для каждого из q дней Фермер Джон хотел бы знать сумму по всем возможным способам выбрать k типов, максимального количества грядок, которое он может сделать для этого подмножества типов. Поскольку это число может быть достаточно большим, выведите его по модулю 109 + 7.
Выходные данные
Для каждого из q дней выведите сумму максимально возможного количества грядок по всем способам выбрать ровно k типов цветов. Ответ выводите по модулю 109 + 7.
Примечание
В первом примере 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 для второго.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 2
4
6
9
8
6
|
5
16
|
|
2
|
4 1 2
6
5
4
3
2
1
|
20
21
|