差分与前缀和

题目描述

给定一个长为 $n$ 的序列 $a$,求出其 $k$ 阶差分或前缀和。 结果的每一项都需要对 $1004535809$ 取模。

输入输出格式

输入格式


第一行三个整数 $n,k,t$,若 $t=0$ 表示求前缀和,$t=1$ 表示求差分。 第二行 $n$ 个整数,表示序列 $a$。

输出格式


输出一行 $n$ 个整数,表示 $a$ 的 $k$ 阶差分或前缀和。

输入输出样例

输入样例 #1

8 3 0
1 9 2 6 0 8 1 7

输出样例 #1

1 12 35 76 135 220 332 478 

输入样例 #2

8 3 1
1 9 2 6 0 8 1 7

输出样例 #2

1 6 1004535787 26 1004535788 24 1004535780 28

说明

【数据范围】 $1 \le n \le 10^5$ $0 \le a_i \le 10^9$ $1\le k \le 10^{2333}, k \not \equiv 0 \pmod{1004535809}$