можно ссылку на задачу?

Понятно, что в итоговом массиве каждое из чисел $$$a_k$$$ войдет с каким-то неотрицательным коэффициентом. Зафиксируем $$$a_k$$$ и вычислим для каждого элемента итогового массива этот коэффициент.

Пусть $$$dp[i][j]$$$ — коэффициент, с которым элемент $$$a_0$$$ войдет в $$$j$$$-й элемент массива, полученного через $$$i$$$ итераций. Нетрудно понять, что $$$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$$$. $$$dp[i][0] = dp[i - 1][0]$$$, а $$$dp[0][i] = 1$$$. Теперь $$$i$$$-му элементу результирующего массива нужно прибавить $$$a_0 \cdot dp[k][i]$$$. Теперь проследим, что изменится, когда мы будем считать коэффициенты для $$$a_1$$$. Нетрудно понять, что элементы динамики в каждой строке как бы сдвинутся на $$$1$$$ вправо, а $$$0$$$-й столбец заполнится нулями. Таким образом, если $$$a_0$$$ входит в элемент $$$i$$$ с коэффициентом $$$dp[k][i]$$$, то $$$a_1$$$ будет входить с коэффициентом $$$dp[k][i - 1]$$$, $$$a_2$$$ — с коэффициентом $$$dp[k][i - 2]$$$, и так далее.

Осталось научиться быстро считать $$$dp[k][i]$$$. Для этого можно посмотреть на формулу: $$$dp[k][i] = dp[k - 1][i] + dp[k][i - 1]$$$. Можно заметить, что $$$dp[k][i] = \binom{k+i}{i}$$$ (действительно, $$$\binom{k+i}{i} = \binom{k+i-1}{i} + \binom{k+i-1}{i-1}$$$). То есть нужно научиться считать $$$\binom{k+i}{i}$$$, где $$$k \leq 10^9$$$, а $$$i \leq 2000$$$. Можно посчитать его по определению: $$$\frac{(k+i)(k+i-1) \cdot \ldots \cdot (k + 1)}{i(i-1) \cdot \ldots \cdot 1}$$$. Можно предподсчитать $$$\binom{k+i}{i}$$$ для всех $$$i$$$ суммарно за $$$O(n^2)$$$. (Во всех формулах из-за 0-индексации нужно уменьшить $$$k$$$ на единицу.)

После этого останется по выведенным формулам посчитать ответ. Переберем элемент $$$a_i$$$, после чего добавим в $$$j$$$-й элемент значение $$$a_i$$$, умноженное на нужный биномиальный коэффициент. Не забываем аккуратно считать по модулю. Итого $$$O(n^2)$$$.