#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=1e2+1;
const int M=1e9+7;
const ll MOD=1ll*M*M;
struct mat{
int a[N][N];
mat(){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++)
a[i][j]=0;
}
}
mat operator *(const mat &o){
mat c;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
ll cur=0;
for(int k=0;k<N;k++){
cur+=1ll*a[i][k]*o.a[k][j];
if(cur>=MOD)
cur-=MOD;
}
c.a[i][j]=cur%M;
}
}
return c;
}
};
mat binpow(mat a,int x,ll k){
mat ans;
ans.a[x][x]=1;
while(k){
if(k&1) ans=ans*a;
a=a*a;k>>=1;
}
return ans;
}
int binpowt(int a,int b){
int ans=1;
while(b){
if(b&1) ans=1ll*ans*a%M;
a=1ll*a*a%M;b>>=1;
}
return ans;
}
int C[N][N];
int inv(int x){
return binpowt(x,M-2);
}
int mult(int a,int b){
return 1ll*a*b%M;
}
int di[10];
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
di[1]=0+2+0+0+0;
di[2]=1+0+0+8+0;
di[3]=1+2+4+0+0;
di[4]=0+2+0+0+16;
di[5]=1+0+4+0+16;
di[6]=0+0+4+8+0;
di[7]=1+2+0+0+0;
di[8]=1+0+4+8+16;
di[9]=1+2+4+0+16;
di[0]=0+2+0+8+0;
C[0][0]=1;
for(int i=1;i<N;i++){
for(int j=0;j<=i;j++){
C[j][i]=C[j][i-1]+(j?C[j-1][i-1]:0);
C[j][i]%=M;
}
}
int m;ll n,k;
int x;
cin>>m>>n>>k>>x;
mat me;
for(int i=0;i<=5*m;i++){
if((i-1)>=0)
me.a[i][i-1]=5*m-i+1;
if(i+1<=(5*m))
me.a[i][i+1]=i+1;
// for(int j=0;j<=5*m;j++)
// cout<<me.a[i][j]<<' ';
// cout<<endl;
}
mat yo=binpow(me,0,k);
mat yo1=binpow(me,0,n%k);
mat o,o1;
for(int i=0;i<(m==1?10:100);i++){
for(int j=0;j<(m==1?10:100);j++){
int fi=(m==1?__builtin_popcount(di[i]^di[j]):__builtin_popcount(di[i%10]^di[j%10])+__builtin_popcount(di[i/10]^di[j/10]));
o.a[i][j]=mult(1,yo.a[0][fi]);
// cout<<"GO "<<i<<' '<<j<<' '<<' '<<fi<<' '<<o.a[i][j]<<' '<<C[fi][5*m]<<endl;
o1.a[i][j]=mult(1,yo1.a[0][fi]);
}
}
// for(int i=0;i<(m==1?10:100);i++){
// for(int j=0;j<(m==1?10:100);j++){
// cout<<o.a[i][j]<<' ';
// }
// cout<<'\n';
// }
o=binpow(o,x,n/k);
// for(int i=0;i<(m==1?10:100);i++){
// for(int j=0;j<(m==1?10:100);j++){
// cout<<o.a[i][j]<<' ';
// }
// cout<<'\n';
// }
o=o*o1;
for(int x=0;x<(m==1?10:100);x++){
int cur=0;
for(int y=0;y<(m==1?10:100);y++){
cur+=o.a[y][x];
cur%=M;
}
cout<<cur<<'\n';
}
return 0;
}
/*
10 1
2 5 8 4 10 7 9 6 1
3
1 4
*/
