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}$.

제한

힌트