K-th Order Difference or Prefix Sum

Given a sequence \(a\) of length \(n\), compute its \(k\)-th order difference if \(k \ge 0\), or compute the prefix sum iteratively \(|k|\) times if \(k < 0\). Each element of the resulting sequence should be taken modulo \(1004535809\).

For the difference operation, if \(a = [a_0, a_1, \dots, a_{n-1}]\), the first order difference is \([a_1 - a_0, a_2 - a_1, \dots, a_{n-1} - a_{n-2}]\). Higher order differences are computed by repeatedly applying the difference operation.

For the prefix sum operation, if \(a = [a_0, a_1, \dots, a_{n-1}]\), the first prefix sum is \([a_0, a_0 + a_1, \dots, a_0 + a_1 + \cdots + a_{n-1}]\). Repeating this operation \(|k|\) times produces the final result.

Note: All arithmetic is performed modulo \(1004535809\).

inputFormat

The first line contains two integers \(n\) and \(k\) where \(n\) is the length of the sequence and \(k\) determines the operation:

• If \(k \ge 0\), perform \(k\) iterations of difference operations.
• If \(k < 0\), perform \(|k|\) iterations of prefix sum operations.

The second line contains \(n\) space-separated integers representing the sequence \(a\).

outputFormat

Output the resulting sequence after performing all operations. The numbers should be space-separated.

sample

5 1
1 2 4 7 11

1 2 3 4