#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
struct matrix
{
int v[100][100];
};
matrix operator*(matrix x, matrix y)
{
matrix aux;
for(int i=0;i<100;i++)
{
for(int j=0;j<100;j++)
{
aux.v[i][j]=0;
for(int k=0;k<100;k++)
{
aux.v[i][j] += aux.v[i][k] * aux.v[k][j];
aux.v[i][j]%=MOD;
}
}
}
return aux;
}
matrix put(matrix a, int exp)
{
if(exp==1)
return a;
if(exp%2==0)
return put(a*a,exp/2);
else
return put(a*a,exp/2)*a;
}
int m;
map<pair<int,int>,pair<int,bool>> mp;
int dp[12][1505];
int put_nr(int a, int exp)
{
if(exp==0)
return 1;
if(exp%2==0)
return put_nr(a*a%MOD,exp/2);
else
return put_nr(a*a%MOD,exp/2)*a%MOD;
}
int fact[3005],invf[3005];
int comb(int x, int y)
{
if(x<y)
return 0;
return ((((fact[x]*invf[y])%MOD)*invf[x-y])%MOD);
}
int calc(int cnt1, int k)
{
dp[0][0]=1;
for(int i=1;i<=cnt1;i++)
{
for(int nr=0;nr<=k;nr++)
{
dp[i][nr]=0;
for(int cur=1;cur<=nr;cur+=2)
{
dp[i][nr] += dp[i-1][nr-cur] * comb(nr,cur);
dp[i][nr]%=MOD;
}
}
}
for(int i=cnt1+1;i<=10;i++)
{
for(int nr=0;nr<=k;nr++)
{
dp[i][nr]=0;
for(int cur=0;cur<=nr;cur+=2)
{
dp[i][nr] += dp[i-1][nr-cur] * comb(nr,cur);
dp[i][nr]%=MOD;
}
}
}
return dp[10][k];
}
int getmp(int config, int k)
{
int cnt1=0;
for(int i=0;i<10;i++)
if(((1<<i)&config))
cnt1++;
if(mp[{cnt1,k}].second==0)
{
mp[{cnt1,k}]={calc(cnt1,k),1};
}
return mp[{cnt1,k}].first;
}
int mask[100];
matrix calc_matrix(int k)
{
matrix aux;
for(int i=0;i<100;i++)
{
for(int j=0;j<100;j++)
{
aux.v[i][j] = getmp(mask[i]^mask[j],k);
}
}
return aux;
}
void calc_mask()
{
mask[0] = (1<<1) + (1<<3);
mask[1] = (1<<1);
mask[2] = (1<<0) + (1<<3);
mask[3] = (1<<0) + (1<<1) + (1<<2);
mask[4] = (1<<1) + (1<<4);
mask[5] = (1<<0) + (1<<2) + (1<<4);
mask[6] = (1<<2) + (1<<3);
mask[7] = (1<<0) + (1<<1);
mask[8] = (1<<0) + (1<<2) + (1<<3) + (1<<4);
mask[9] = (1<<0) + (1<<1) + (1<<2) + (1<<4);
for(int i=10;i<100;i++)
{
mask[i] = (mask[i/10]<<5) + mask[i%10];
}
}
signed main()
{
fact[0]=1;
for(int i=1;i<=3000;i++)
fact[i]=fact[i-1]*i%MOD;
invf[3000]=put_nr(fact[3000],MOD-2);
for(int i=2999;i>=0;i--)
invf[i]=invf[i+1]*(i+1)%MOD;
int n,k,x;
cin>>m>>n>>k>>x;
calc_mask();
matrix km = calc_matrix(k);
matrix rm = calc_matrix(n%k);
matrix rez;
for(int i=0;i<100;i++)
for(int j=0;j<100;j++)
rez.v[i][j]=0;
rez.v[x][0]=1;
if(n/k > 0) rez = rez*put(km,n/k);
if(n%k > 0) rez = rez*rm;
if(n==k) rez=km;
for(int i=0;i<100;i++)
{
if(m==1 && i>=10)
break;
cout<<rez.v[x][i]<<"\n";
}
return 0;
}
/**
input: 2 10 10 79
*/
Compilation message
/usr/bin/ld: /tmp/cc1R6GLs.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccPqbU9u.o:swaps.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc1R6GLs.o: in function `main':
grader.cpp:(.text.startup+0x67): undefined reference to `solve(int, int)'
collect2: error: ld returned 1 exit status
