/*
// is short or still long ???
hollwo_pelw's template(short)
// Note : -Dhollwo_pelw_local
*/
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
void FAST_IO(string filein = "", string fileout = "", string fileerr = ""){
if (fopen(filein.c_str(), "r")){
freopen(filein.c_str(), "r", stdin);
freopen(fileout.c_str(), "w", stdout);
#ifdef hollwo_pelw_local
freopen(fileerr.c_str(), "w", stderr);
#endif
}
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
}
void Hollwo_Pelw();
signed main(){
#ifdef hollwo_pelw_local
FAST_IO("input.inp", "output.out", "error.err");
auto start = chrono::steady_clock::now();
#else
FAST_IO("semafor.inp", "semafor.out");
#endif
int testcases = 1;
// cin >> testcases;
for (int test = 1; test <= testcases; test++){
// cout << "Case #" << test << ": ";
Hollwo_Pelw();
}
#ifdef hollwo_pelw_local
auto end = chrono::steady_clock::now();
cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
return 0;
}
#define defop(type, op) \
friend inline type operator op (type a, const type &b) { return a op##= b; } \
type& operator op##= (const type &oth)
template<class T> struct mod_int {
constexpr int mod() { return T::mod; }
int v;
mod_int(long long _v = 0)
: v(norm(_v)) {}
inline int norm(long long a) {
return a < 0 ? a % mod() + mod() : a % mod();
}
mod_int neg() const { return v == 0 ? 0 : mod() - v; }
template <typename U>
explicit operator U() const { return v; }
mod_int operator - () const { return neg(); }
mod_int operator + () const { return mod_int(*this); }
mod_int& operator -- () { if (v == 0) v = mod(); -- v; return *this; }
friend mod_int operator -- (mod_int& a, int) { mod_int r = a; --a; return r; }
mod_int& operator ++ () { ++ v; if (v == mod()) v = 0; return *this; }
friend mod_int operator ++ (mod_int& a, int) { mod_int r = a; ++a; return r; }
defop(mod_int, +) {
if ((v += oth.v) >= mod()) v -= mod();
return *this;
}
defop(mod_int, -) {
if ((v -= oth.v) < 0) v += mod();
return *this;
}
defop(mod_int, *) {
return *this = norm(1ll * v * oth.v);
}
mod_int pow(long long b) const {
mod_int a = *this, r = 1;
while (b) {
if (b&1) r *= a;
b >>= 1; a *= a;
}
return r;
}
mod_int inv() const { return pow(mod() - 2); }
defop(mod_int, /) {
return *this *= oth.inv();
}
#define compare(op) friend bool operator op \
(const mod_int& lhs, const mod_int& rhs) { return lhs.v op rhs.v; }
compare(==) compare(!=) compare(<) compare(<=) compare(>) compare(>=)
#undef compare
friend std::ostream& operator << (std::ostream& out, const mod_int& n) { return out << int(n); }
friend std::istream& operator >> (std::istream& inp, mod_int& n) { long long x; inp >> x; n = mod_int(x); return inp; }
};
struct modular { static constexpr int mod = static_cast<int>(1e9 + 7); };
// struct modular { static int mod; };
// int modular::mod;
using Mint = mod_int<modular>;
struct matrix {
vector<vector<Mint>> a;
size_t size() { return a.size(); }
vector<Mint>& operator [] (int x) {return a[x];}
const vector<Mint>& operator [] (int x) const {return a[x];}
matrix(int sz = 0, int v = 0) {
a.assign(sz, vector<Mint>(sz));
if (v) for (int i = 0; i < sz; i++) a[i][i] = v;
}
};
matrix operator * (matrix a, matrix b) {
int sz = a.size();
matrix c(sz);
for (int i = 0; i < sz; i++) {
for (int j = 0; j < sz; j++) {
for (int k = 0; k < sz; k++)
c[i][j] += a[i][k] * b[k][j];
}
}
return c;
}
matrix operator ^ (matrix a, int64_t b) {
int sz = a.size();
matrix r(sz, 1);
while (b) {
if (b&1) r = r * a;
b >>= 1; a = a * a;
}
return r;
}
const int num[10] = {
0b01010, // 0
0b00010, // 1
0b01001, // 2
0b00111, // 3
0b10010, // 4
0b10101, // 5
0b01100, // 6
0b00011, // 7
0b11101, // 8
0b10111 // 9
};
int m, x, d, cnt;
int64_t n, k;
inline int tomask(int v) {
return m == 1 ? num[v] : num[v % 10] << 5 | num[v / 10];
}
inline int dist(int a, int b) {
return __builtin_popcount(tomask(a) ^ tomask(b));
}
matrix get_tran(const matrix& a) {
matrix base(cnt);
for (int i = 0; i < cnt; i++)
for (int j = 0; j < cnt; j++)
base[i][j] = a[0][dist(i, j)];
return base;
}
void Hollwo_Pelw() {
cin >> m >> n >> k >> x;
cnt = m == 1 ? 10 : 100, d = m * 5;
// free move in kth period
matrix base(d + 1);
for (int i = 0; i < d; i++) {
base[i][i + 1] = i + 1;
base[i + 1][i] = d - i;
}
matrix full = base ^ k;
matrix left = base ^ (n % k);
matrix res = (get_tran(full) ^ (n / k)) * get_tran(left);
for (int i = 0; i < cnt; i++)
cout << res[x][i] << '\n';
}
