Числа Фибоначчи и запросы
(Время: 0,5 сек. Память: 32 Мб Сложность: 80%)
Последовательностью Фибоначчи называется последовательность чисел F1, F2, ..., Fn, ..., где F1 = F2 = 1, Fm = Fm-1 + Fm-2 (m > 2).
Необходимо ответить на q запросов, каждый из которых имеет вид Fk×n.
Входные данные
Входной файл INPUT.TXT содержит в первой строке два натуральных числа n, q (1 ≤ n ≤ 109; 1 ≤ q ≤ 106).
Во второй строке находятся q чисел ki (1 ≤ ki ≤ 109; 1 ≤ i ≤ q).
Выходные данные
В выходной файл OUTPUT.TXT выведите q чисел через пробел F(ki×n) по модулю 109 + 7.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 3
1 2 3 | 3 21 144 |
Пояснение к примеру
F(1×4) = 4, F(2×4) = 21, F(3×4) = 144.
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
