21686번 - Таблица 다국어

Рассмотрим прямоугольную таблицу $n$ на $m$. Занумеруем строки таблицы числами от $1$ до $n$, а столбцы – числами от $1$ до $m$. Таблица последовательно заполняется числами. Обозначим через $a_{i,j}$ число, стоящее на пересечении $i$-ой строки и $j$-ого столбца. Первая строка таблицы заполняется заданными числами – $a_{1,1}, a_{1,2}, \cdots , a_{1,m}$. Затем заполняются строки с номерами от $2$ до $n$. Число $a_{i,j}$ вычисляется как сумма всех чисел таблицы, находящихся в «треугольнике» над элементом $a_{i,j}$. Все вычисления при этом выполняются по модулю $r$.

Более точно, значение $a_{i,j}$ вычисляется по следующей формуле:

Например, если таблица состоит из трех строк и четырех столбцов, и первая строка состоит из чисел $2$,$3$,$4$,$5$, а $r = 40$ то таблица выглядит следующим образом (взятие по модулю показано только там, где оно приводит к изменению числа):

Дана первая строка таблицы $(a_{1,1}, a_{1,2}, \cdots , a_{1,m})$, требуется вычислить последнюю строку. Поскольку числа в ответе могут быть достаточно большими, посчитайте ответ по модулю r.

Первая строка входного файла содержит числа $n$, $m$ и $r$ ($2 \le n, m \le 2000, 2 \le r \le 10^9$) – число строк и столбцов таблицы соответственно, а так же число, по модулю которого надо посчитать ответ. Следующая строка содержит $m$ целых чисел – первую строку таблицы: $a_{1,1}, a_{1,2}, \cdots, a_{1,m}$. Все $a_{1,i}$ неотрицательны и не превосходят $10^9$.

Выведите в первой строке выходного файла $m$ чисел – последнюю строку таблицы: $a_{n,1}, a_{n,2}, \cdots , a_{n,m}$.