#include using namespace std; using ll = long long; using uint = unsigned int; using ull = unsigned long long; #define rep(i,n) for(int i=0;i=0;i--) #define per1(i,n) for(int i=int(n);i>0;i--) #define all(c) c.begin(),c.end() #define si(x) int(x.size()) #define pb push_back #define eb emplace_back #define fs first #define sc second template using V = vector; template using VV = vector>; template bool chmax(T& x, U y){ if(x bool chmin(T& x, U y){ if(y void mkuni(V& v){sort(all(v));v.erase(unique(all(v)),v.end());} template int lwb(const V& v, const T& a){return lower_bound(all(v),a) - v.begin();} template V Vec(size_t a) { return V(a); } template auto Vec(size_t a, Ts... ts) { return V(ts...))>(a, Vec(ts...)); } template ostream& operator<<(ostream& o,const pair &p){ return o<<"("< ostream& operator<<(ostream& o,const vector &vc){ o<<"{"; for(const T& v:vc) o< D divFloor(D a, D b){ return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0); } template D divCeil(D a, D b) { return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0); } template struct ModInt{ using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr static uint mod = mod_; uint v; ModInt():v(0){} ModInt(ll _v):v(normS(_v%mod+mod)){} explicit operator bool() const {return v!=0;} static uint normS(const uint &x){return (x [0 , mod-1] static ModInt make(const uint &x){ModInt m; m.v=x; return m;} ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));} ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));} ModInt operator-() const { return make(normS(mod-v)); } ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);} ModInt operator/(const ModInt& b) const { return *this*b.inv();} ModInt& operator+=(const ModInt& b){ return *this=*this+b;} ModInt& operator-=(const ModInt& b){ return *this=*this-b;} ModInt& operator*=(const ModInt& b){ return *this=*this*b;} ModInt& operator/=(const ModInt& b){ return *this=*this/b;} ModInt& operator++(int){ return *this=*this+1;} ModInt& operator--(int){ return *this=*this-1;} template friend ModInt operator+(T a, const ModInt& b){ return (ModInt(a) += b);} template friend ModInt operator-(T a, const ModInt& b){ return (ModInt(a) -= b);} template friend ModInt operator*(T a, const ModInt& b){ return (ModInt(a) *= b);} template friend ModInt operator/(T a, const ModInt& b){ return (ModInt(a) /= b);} ModInt pow(ll p) const { if(p<0) return inv().pow(-p); ModInt a = 1; ModInt x = *this; while(p){ if(p&1) a *= x; x *= x; p >>= 1; } return a; } ModInt inv() const { // should be prime return pow(mod-2); } // ll extgcd(ll a,ll b,ll &x,ll &y) const{ // ll p[]={a,1,0},q[]={b,0,1}; // while(*q){ // ll t=*p/ *q; // rep(i,3) swap(p[i]-=t*q[i],q[i]); // } // if(p[0]<0) rep(i,3) p[i]=-p[i]; // x=p[1],y=p[2]; // return p[0]; // } // ModInt inv() const { // ll x,y; // extgcd(v,mod,x,y); // return make(normS(x+mod)); // } bool operator==(const ModInt& b) const { return v==b.v;} bool operator!=(const ModInt& b) const { return v!=b.v;} bool operator<(const ModInt& b) const { return v>(istream &o,ModInt& x){ ll tmp; o>>tmp; x=ModInt(tmp); return o; } friend ostream& operator<<(ostream &o,const ModInt& x){ return o<; // inplace_fmt (without bit rearranging) // fft: // a[rev(i)] <- \sum_j \zeta^{ij} a[j] // invfft: // a[i] <- (1/n) \sum_j \zeta^{-ij} a[rev(j)] // These two are inversions. // !!! CHANGE IF MOD is unusual !!! const int ORDER_2_MOD_MINUS_1 = 20; // ord_2 (mod-1) const mint PRIMITIVE_ROOT = 6; // primitive root of (Z/pZ)* void fft(V& a){ static constexpr uint mod = mint::mod; static constexpr uint mod2 = mod + mod; static const int H = ORDER_2_MOD_MINUS_1; static const mint root = PRIMITIVE_ROOT; static mint magic[H-1]; int n = si(a); assert(!(n & (n-1))); assert(n >= 1); assert(n <= 1<>(i+2))*3); magic[i] = w; } } int m = n; if(m >>= 1){ rep(i,m){ uint v = a[i+m].v; // < M a[i+m].v = a[i].v + mod - v; // < 2M a[i].v += v; // < 2M } } if(m >>= 1){ mint p = 1; for(int h=0,s=0; s>= 1){ mint p = 1; for(int h=0,s=0; s>= 1){ mint p = 1; for(int h=0,s=0; s= mod2) ? a[i].v - mod2 : a[i].v; // < 2M a[i+m].v = a[i].v + mod - v; // < 3M a[i].v += v; // < 3M } p *= magic[__builtin_ctz(++h)]; } } } rep(i,n){ a[i].v = (a[i].v >= mod2) ? a[i].v - mod2 : a[i].v; // < 2M a[i].v = (a[i].v >= mod) ? a[i].v - mod : a[i].v; // < M } // finally < mod !! } void invfft(V& a){ static constexpr uint mod = mint::mod; static constexpr uint mod2 = mod + mod; static const int H = ORDER_2_MOD_MINUS_1; static const mint root = PRIMITIVE_ROOT; static mint magic[H-1]; int n = si(a); assert(!(n & (n-1))); assert(n >= 1); assert(n <= 1<>(i+2))*3); magic[i] = w.inv(); } } int m = 1; if(m < n>>1){ mint p = 1; for(int h=0,s=0; s>1; m <<= 1){ mint p = 1; for(int h=0,s=0; s>1);i++){ ull x = a[i].v + mod2 - a[i+m].v; // < 4M a[i].v += a[i+m].v; // < 4M a[i].v = (a[i].v >= mod2) ? a[i].v - mod2 : a[i].v; // < 2M a[i+m].v = (p.v * x) % mod; // < M } for(int i=s+(m>>1); i calc_magic(const vector& ns){ int k = si(ns); if(k == 0) return {}; int n = 1; for(int ni: ns) n *= ni; V magic(n); rep(i,n){ int x = i; rep(j,k){ magic[i] += x; x /= ns[j]; } magic[i] %= k; } return magic; } vector multivariate_mult(const vector& f, const vector& g, const vector& ns, const vector& magic){ assert(si(f) == si(g)); int n = si(f); int k = si(ns); if(k == 0){ return {f[0]*g[0]}; } int s = 1; while(s h(n); vector> zf(k,vector(s)); vector> zg(k,vector(s)); vector> zh(k,vector(s)); rep(i,n) zf[magic[i]][i] = f[i]; rep(i,k) fft(zf[i]); rep(i,n) zg[magic[i]][i] = g[i]; rep(i,k) fft(zg[i]); rep(a,k) rep(b,k){ int c = (a+b)%k; rep(i,s) zh[c][i] += zf[a][i] * zg[b][i]; } rep(i,k) invfft(zh[i]); rep(i,n) h[i] = zh[magic[i]][i]; return h; } vector multivariate_log(const vector& f, const vector& ns, const vector& magic){ exit(1); } V tens = {1,10,100,1000,10000,100000}; V zs; vector mult(vector f, vector g, int A,int B, bool za, bool zb, bool zc){ int n = si(f); auto zeta10 = [&](V f){ V g(10); rep(i,10) rep(j,10) g[i] += f[j] * zs[i*j]; return g; }; auto izeta10 = [&](V f){ const static mint i10 = mint(10).inv(); V g(10); rep(i,10) rep(j,10) g[i] += f[j] * zs[90-i*j] * i10; return g; }; auto zeta = [&](vector f){ for(int d=A;d buf(10); rep(i,10) buf[i] = f[s+tens[d]*i]; buf = zeta10(buf); rep(i,10) f[s+tens[d]*i] = buf[i]; } } return f; }; auto izeta = [&](vector f){ for(int d=A;d buf(10); rep(i,10) buf[i] = f[s+tens[d]*i]; buf = izeta10(buf); rep(i,10) f[s+tens[d]*i] = buf[i]; } } return f; }; if(!za) f = zeta(f); if(!zb) g = zeta(g); V zf(tens[A]), zg(tens[A]),zh; V ns(A,10); V magic = calc_magic(ns); rep(s,si(f)) if(s%tens[A] == 0){ rep(i,tens[A]) zf[i] = f[s+i], zg[i] = g[s+i]; zh = multivariate_mult(zf,zg,ns,magic); // show(zf);show(zg);show(zh); // show(ns);show(magic); // show("------------"); rep(i,tens[A]) f[s+i] = zh[i]; } if(!zc) f = izeta(f); return f; } template > constexpr T power(T a, uint64_t n, T init = 1, Op op = Op{}) { while (n) { if (n & 1) init = op(init, a); if (n >>= 1) a = op(a, a); } return init; } int main(){ cin.tie(0); ios::sync_with_stdio(false); //DON'T USE scanf/printf/puts !! cout << fixed << setprecision(20); int N,A,B; ll X; { int K; cin >> N; cin >> K; cin >> X; int T; cin >> T; A = T, B = K-T; } { mint z = mint(6).pow((mint::mod-1)/10); rep(i,91) zs.pb(z.pow(i)); } V f(TEN(A+B)); while(N--){ int x; cin >> x; f[x]++; } auto mul = [&](auto x,auto y,bool za,bool zb,bool zc){ return mult(x,y,A,B,za,zb,zc); }; V id(TEN(A+B)); id[0] = 1; // f = power(f,X,id,mul); // for(auto v: f) cout << v << endl; V f0(TEN(A+B)),f1(TEN(A+B)); rep(s,TEN(A+B)){ if(s%TEN(A) == 0) f0[s] = f[s]; else f1[s] = f[s]; } ll XX = max(X-45,0LL); ll work = X-XX; VV f1pow(work+1); f1pow[0] = id; rep1(i,work) f1pow[i] = mul(f1pow[i-1], f1, 0,0,0); int n = si(f); auto zeta10 = [&](V f){ V g(10); rep(i,10) rep(j,10) g[i] += f[j] * zs[i*j]; return g; }; auto izeta10 = [&](V f){ const static mint i10 = mint(10).inv(); V g(10); rep(i,10) rep(j,10) g[i] += f[j] * zs[90-i*j] * i10; return g; }; auto zeta = [&](vector f){ for(int d=A;d buf(10); rep(i,10) buf[i] = f[s+tens[d]*i]; buf = zeta10(buf); rep(i,10) f[s+tens[d]*i] = buf[i]; } } return f; }; auto izeta = [&](vector f){ for(int d=A;d buf(10); rep(i,10) buf[i] = f[s+tens[d]*i]; buf = izeta10(buf); rep(i,10) f[s+tens[d]*i] = buf[i]; } } return f; }; show(f0); show(f1); show(f1pow); show(XX); VV gs(work+1); if(true){ auto g0 = zeta(f0); V g(TEN(A+B)); rep(s,n) if(s%TEN(A) == 0) g[s] = g0[s].pow(XX); rep(i,work+1){ gs[work-i] = g; rep(s,n) g[s] *= g0[s]; } } show(gs); V ans(TEN(A+B)); mint choose = 1; rep(i,work+1){ auto p = mul(f1pow[i],gs[i],0,1,0); rep(s,n) ans[s] += p[s] * choose; choose *= X-i; choose /= i+1; } rep(s,n) cout << ans[s] << endl; }