满江红。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
#define for1(i,a,b) for(int i=(a);i<=(b);++i)
#define for2(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=500010,mod=1004535809,inv3=55924054;
int n,k,op,lim=1,invl,r[N],a[N],b[N];
inline int qp(int a,int b,int ret=1) {
	while(b) {if(b&1) ret=ret*a%mod;a=a*a%mod,b>>=1;}
	return ret;
}
void NTT(int *a,bool flag) {
	for1(i,0,lim-1) if(i<r[i]) swap(a[i],a[r[i]]);
	for(int i=1;i<lim;i<<=1) {
		int rt=qp(flag?inv3:3,(mod-1)/(i<<1));
		for(int j=i<<1,p=0,w=1;p<lim;p+=j,w=1)
			for(int k=0;k<i;++k,w=w*rt%mod) {
				int x=a[p+k],y=w*a[p+i+k]%mod;
				a[p+k]=(x+y)%mod,a[p+i+k]=(x-y+mod)%mod;
			}
	}
}
signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k>>op,b[0]=1;
	for1(i,0,n-1) cin>>a[i];
	if(op) {
		for1(i,1,n-1) b[i]=b[i-1]*qp(i,mod-2)%mod*(k-i+1)%mod;
		for(int i=1;i<n;i+=2) b[i]=mod-b[i];
	}
	else for1(i,1,n-1) b[i]=b[i-1]*qp(i,mod-2)%mod*(k+i-1)%mod;
	while(lim<n+n) lim<<=1;
	invl=qp(lim,mod-2);
	for1(i,0,lim-1) r[i]=(r[i>>1]>>1)|(i&1?lim>>1:0);
	NTT(a,0),NTT(b,0);
	for1(i,0,lim-1) a[i]=a[i]*b[i]%mod;
	NTT(a,1);
	for1(i,0,n-1) cout<<(a[i]*invl%mod+mod)%mod<<' ';
	return 0;
}