#include <stdio.h>
#include <string.h>
#define N 100
#define MD 1000000007
#define B 32
int count[B];
int mask[] = { 10, 2, 9, 7, 18, 21, 12, 3, 29, 23 };
int vch5[] = { 1, 5, 10, 10, 5, 1 };
int vch10[] = { 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1 };
int inv(int a) {
return a == 1 ? 1 : (long long) inv(a - MD % a) * (MD / a + 1) % MD;
}
void init() {
int b, i;
for (b = 1; b < B; b++)
count[b] = count[b & b - 1] + 1;
for (i = 0; i <= 5; i++)
vch5[i] = inv(vch5[i]);
for (i = 0; i <= 10; i++)
vch10[i] = inv(vch10[i]);
}
void mult(int aa[][N], int bb[][N], int cc[][N], int n) {
int i, j, k;
for (i = 0; i < n; i++)
memset(cc[i], 0, n * sizeof *cc[i]);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
int a = aa[i][j];
if (a == 0)
continue;
for (k = 0; k < n; k++) {
int b = bb[j][k];
if (b != 0)
cc[i][k] = (cc[i][k] + (long long) a * b) % MD;
}
}
}
void power(int aa[][N], int pp[][N], int tt[][N], int n, long long k) {
if (k == 0) {
int i;
for (i = 0; i < n; i++)
memset(pp[i], 0, n * sizeof *pp[i]), pp[i][i] = 1;
return;
}
if (k % 2 == 0) {
power(aa, tt, pp, n, k / 2);
mult(tt, tt, pp, n);
} else {
power(aa, pp, tt, n, k / 2);
mult(pp, pp, tt, n);
mult(tt, aa, pp, n);
}
}
int main() {
static int aa[N][N], bb[N][N], cc[N][N], pp[N][N], tt[N][N];
int n, m, s, i, j, c;
long long k, l;
init();
scanf("%d%lld%lld%d", &m, &k, &l, &s), n = m == 1 ? 10 : 100;
for (c = 0; c <= m * 5; c++) {
if (c < m * 5)
aa[c][c + 1] = m * 5 - c;
if (c > 0)
aa[c][c - 1] = c;
}
power(aa, pp, tt, m * 5 + 1, l);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (m == 1) {
c = count[mask[i] ^ mask[j]];
bb[i][j] = (long long) pp[0][c] * vch5[c] % MD;
} else {
c = count[mask[i / 10] ^ mask[j / 10]] + count[mask[i % 10] ^ mask[j % 10]];
bb[i][j] = (long long) pp[0][c] * vch10[c] % MD;
}
power(bb, cc, tt, n, k / l);
power(aa, pp, tt, m * 5 + 1, k % l);
for (j = 0; j < n; j++) {
int ans;
ans = 0;
for (i = 0; i < n; i++) {
int x;
if (m == 1) {
c = count[mask[i] ^ mask[j]];
x = (long long) pp[0][c] * vch5[c] % MD;
} else {
c = count[mask[i / 10] ^ mask[j / 10]] + count[mask[i % 10] ^ mask[j % 10]];
x = (long long) pp[0][c] * vch10[c] % MD;
}
ans = (ans + (long long) cc[s][i] * x) % MD;
}
printf("%d\n", ans);
}
return 0;
}
