C. Частичные суммы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив a, состоящий из n целых чисел. Элементы массива проиндексированы от 1 до n. Определим операцию, которая состоит из двух шагов, следующим образом:

  1. Сначала по массиву a строится массив s частичных сумм, состоящий из n элементов. Элемент номер i (1 ≤ i ≤ n) массива s равен . Операция x mod y обозначает взятие остатка от деления числа x на число y.
  2. Затем содержимое массива s записывается в массив a. Элемент номер i (1 ≤ i ≤ n) массива s становится i-ым элементом массива a (ai = si).

Вам же нужно найти массив a после применения ровно k описанных операций.

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

В первой строке записаны два целых числа через пробел n и k (1 ≤ n ≤ 2000, 0 ≤ k ≤ 109). В следующей строке записаны n целых чисел через пробел a1, a2, ..., an — элементы массива a (0 ≤ ai ≤ 109).

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

Выведите n целых чисел  — элементы массива a после проделанных операций. Элементы выводите в порядке увеличения их индексов в массиве a. Выведенные числа разделяйте пробельными символами.

Примеры
Входные данные
3 1
1 2 3
Выходные данные
1 3 6
Входные данные
5 0
3 14 15 92 6
Выходные данные
3 14 15 92 6