~~这篇题解对于许多题解打表/一言概括得到的结论进行了充分的证明~~
我们将序列$a$看作一个$OGF$
$$F(x)=\sum_{i=0}^{\infty} a_i x^i$$
考虑计算前缀和，众所周知，只需要拿它乘以$G(x)=1+x^1+...+x^{\infty}$
根据一些等比数列求和的芝士我们知道$G(x)=\dfrac{1}{1-x}$
置于求它的差分，则拿$F$和$1-x$卷起来即可
好了那么$k$维前缀和呢？
$$F\times\dfrac{1}{(1-x)^k}$$
$k$维差分呢？
$$F\times (1-x)^k$$
好了然后求个$\ln$，乘个$k$，取个$\exp$这道题就做完了
但是非常不幸的是这样会非常难写而且我已经不会求$\ln$和$\exp$了（不要问我怎么清$0$，我也不会清$0$）
于是我们还是用点生成函数的技巧吧
首先是差分，它非常好做：
$$(1-x)^k$$
二项式定理强行打开使我们可以知道：
$$(1-x)^k=\sum_{i=0}^{\infty}(-1)^i\dbinom{k}{i}x^i$$
好的这道题真是见了鬼了$k$这么大搞什么。。。
不过这道题要用连续的组合数然而它可以递推
$\dbinom{k}{0}=1,\dbinom{k}{i}=\dbinom{k}{i-1}\times\dfrac{k-i+1}{i}$
然后大概$k$是可以直接取模的。。。
好了接下来是：
$$\dfrac{1}{(1-x)^k}$$
这个有点麻烦，需要借助广义二项式定理：
我们把它看作$(1-x)^{-k}$
根据广义二项式定理它等价于：
$$(1-x)^a=\sum_{i=0}^{\infty}\dbinom{a}{i}x^i$$
这个式子看上去挺对的。。。毕竟当$i>a$的时候$\dbinom{a}{i}=0..$不过现在我们不能用阶乘来定义组合数了，于是我们需要把它改成下降幂的形式：
$$\dbinom{a}{i}=\dfrac{a^{\underline{i}}}{i!}$$
注：$a^{\underline{i}}=a(a-1)(a-2)...(a-i+1)$
好的我们来看下$-k$代入进去是什么样的：
$$(1-x)^{-k}=\sum_{i=0}^{\infty}(-1)^i\dfrac{(-k)^{\underline{i}}}{i!}x^i$$
$$(1-x)^{-k}=\sum_{i=0}^{\infty}(-1)^{2i}\dfrac{(k+i-1)^{\underline{i}}}{i!}x^i$$
所以我们知道：
$$(1-x)^{-k}=\sum_{i=0}^{\infty}\dbinom{k+i-1}{i}x^i$$
好了于是对于差分我们只需要拿$F$和$\sum_{i=0}^{\infty}(-1)^i\dbinom{k}{i}x^i$卷起来即可
对于前缀和我们只需要拿$F$和$\sum_{i=0}^{\infty}\dbinom{k+i-1}{i}x^i$卷起来即可
当然这个什么$\dbinom{k+i-1}{i}$也可以递推，因为它是$\dfrac{(k+i-1)^{\underline{i}}}{i!}$，要递推的话也很简单，每次乘一个$(k+i-1)/i$即可
然后模数还是$\text{NTT}$模数。。。
~~实际上这篇题解是在做一些特别蠢的证明。。。~~
$Code:$
```cpp
#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
const int P = 1004535809 ;
const int Gi = 334845270 ;
const int G = 3 ;
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = ( cn * 10 + cc - '0' ) % P, cc = getchar() ;
return cn * flus ;
}
const int N = 1e5 + 5 ;
int n, m, A[N << 2], B[N << 2], limit, L, Inv, R[N << 2] ;
int fpow( int x, int k ) {
int ans = 1, base = x ;
while( k ) {
if( k & 1 ) ans = ( ans * base ) % P ;
base = ( base * base ) % P, k >>= 1 ;
} return ans ;
}
void init( int x ) {
limit = 1, L = 0 ;
while( limit <= x ) limit <<= 1, ++ L ;
rep( i, 0, limit ) R[i] = ( R[i >> 1] >> 1 ) | ( ( i & 1 ) << ( L - 1 ) ) ;
Inv = fpow( limit, P - 2 ) ;
}
void NTT( int *a, int type ) {
for( re int i = 0; i < limit; ++ i ) if( R[i] > i ) swap( a[i], a[R[i]] ) ;
for( re int k = 1; k < limit; k <<= 1 ) {
int d = fpow( ( type == 1 ) ? G : Gi, ( P - 1 ) / ( k << 1 ) ) ;
for( re int i = 0; i < limit; i += ( k << 1 ) )
for( re int j = i, g = 1 ; j < i + k; ++ j, g = ( g * d ) % P ) {
int Nx = a[j], Ny = ( a[j + k] * g ) % P ;
a[j] = ( Nx + Ny ) % P, a[j + k] = ( Nx - Ny + P ) % P ;
}
}
if( type != 1 ) rep( i, 0, limit ) a[i] = a[i] * Inv % P ;
}
signed main()
{
n = gi(), m = gi() ; int type = gi() ;
rep( i, 1, n ) A[i - 1] = gi() ; B[0] = 1 ;
if( type == 0 ) rep( i, 1, n ) B[i] = B[i - 1] * ( m + i - 1 ) % P * fpow( i, P - 2 ) % P ;
if( type == 1 ) rep( i, 1, n ) B[i] = ( -B[i - 1] * ( m - i + 1 + P ) % P * fpow( i, P - 2 ) % P + P ) % P ;
init( n + n ), NTT( A, 1 ), NTT( B, 1 ) ;
rep( i, 0, limit ) A[i] = A[i] * B[i] % P ;
NTT( A, -1 ) ; rep( i, 1, n ) printf("%lld ", A[i - 1] ) ;
return 0 ;
}
```