Problem Description

Given a sequence \( a \) of length \( n \), compute its \( k \)-th order difference or prefix sum. Each term of the result must be taken modulo \( 1004535809 \).

Input Format

The first line contains three integers \( n, k, t \). If \( t = 0 \), it indicates computing the prefix sum; if \( t = 1 \), it indicates computing the difference.
The second line contains \( n \) integers representing the sequence \( a \).

Output Format

Output one line containing \( n \) integers, representing the \( k \)-th order difference or prefix sum of \( a \).

Sample Input and Output

Sample Input #1

8 3 0
1 9 2 6 0 8 1 7

Sample Output #1

1 12 35 76 135 220 332 478

Sample Input #2

8 3 1
1 9 2 6 0 8 1 7

Sample Output #2

1 6 1004535787 26 1004535788 24 1004535780 28

Notes

[Data Range]

\( 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} \)

见题面 Input 部分

见题面 Output 部分