Слабые группы
(Время: 0,5 сек. Память: 32 Мб Сложность: 88%)
На хакатоне участвуют N человек. Организаторы хотят провести «стресс-тест» структуры знакомств и могут сами сконструировать сеть знакомств следующим образом.
Сначала выбирается число команд R так, что R делит N. Все участники делятся на R команд одинакового размера. Затем организаторы выбирают один из двух режимов знакомств:
- Внутрикомандный режим: знакомы только участники внутри одной команды, между разными командами знакомств нет.
- Межкомандный режим: знакомы только участники из разных команд, внутри команды знакомств нет.
После этого тестировщики выбирают K участников. Рассматриваются все пары внутри выбранной группы. Пара считается «знакомой», если между этими двумя участниками есть знакомство по выбранной структуре. Группа из K человек называется слабой для числа M, если среди пар внутри группы ровно M знакомых пар.
Вам дано Q запросов – значения M1, M2, …, MQ. Для каждого Mi найдите максимально возможное число слабых групп по модулю 109 + 7, если организаторы могут:
- выбрать любое R такое, что N делится на R,
- выбрать любой режим (внутрикомандный или межкомандный).
Входные данные
Входной файл INPUT.TXT содержит в первой строке три натуральных числа N, K, Q.
Во второй строке содержится Q целых чисел Mi через пробел. (1 ≤ Q, N ≤ 1000; 0 ≤ Mi ≤ 1000; 1 ≤ K ≤ 50).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на каждый запрос по модулю 109 + 7 через пробел.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 6 3 2
1 3 | 18 20 |
| 2 | 8 4 4
1 2 3 10 | 48 36 32 0 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
