Problem Description

Given a sequence $a$ of length $n$, find its $k$-th order difference or prefix sum.
Each term of the result needs to be taken modulo $1004535809$.

Input Format

The first line contains three integers $n, k, t$. If $t = 0$, compute the prefix sum; if $t = 1$, compute the difference.
The second line contains $n$ integers representing the sequence $a$.

Output Format

Output one line with $n$ integers, representing the $k$-th order difference or prefix sum of $a$.

8 3 0
1 9 2 6 0 8 1 7

1 12 35 76 135 220 332 478 

8 3 1
1 9 2 6 0 8 1 7

1 6 1004535787 26 1004535788 24 1004535780 28

Hint

Constraints

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

Translated by ChatGPT 5