Дан массив a, состоящий из n целых чисел. Элементы массива проиндексированы от 1 до n. Определим операцию, которая состоит из двух шагов, следующим образом:
- Сначала по массиву a строится массив s частичных сумм, состоящий из n элементов. Элемент номер i (1 ≤ i ≤ n) массива s равен
. Операция x mod y обозначает взятие остатка от деления числа x на число y. - Затем содержимое массива s записывается в массив a. Элемент номер i (1 ≤ i ≤ n) массива s становится i-ым элементом массива a (ai = si).
Вам же нужно найти массив a после применения ровно k описанных операций.
Выходные данные
Выведите n целых чисел — элементы массива a после проделанных операций. Элементы выводите в порядке увеличения их индексов в массиве a. Выведенные числа разделяйте пробельными символами.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
1 2 3
|
1 3 6
|
|
2
|
5 0
3 14 15 92 6
|
3 14 15 92 6
|