题目描述

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

回忆一下$k$阶前缀和以及$k$阶差分:

考虑序列$S1$是$a$的$1$阶前缀和,那么满足$S1_i=\sum_{j=1}^i a_j$,那么序列$S2$是$a$的$2$阶前缀和,那么满足$S2_i=\sum_{j=1}^iS1_j$,依次类推;

考虑序列$S1$是$a$的$1$阶差分,那么满足$S1_i=a_i-a_{i-1}$,那么序列$S2$是$a$的$2$阶差分,那么满足$S2_i=S1_i-S1_{i-1}$,依次类推;

输入格式

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

输出格式

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

样例 #1

样例输入 #1

8 3 0
1 9 2 6 0 8 1 7

样例输出 #1

1 12 35 76 135 220 332 478

样例 #2

样例输入 #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^{9}$