P5488 Difference and Prefix Sum

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

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 one line with $n$ integers, representing the $k$-th order difference or prefix sum of $a$.

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