#include <iostream>
#include <fstream>
#include <string.h>
#include <math.h>
/*
a) cate numere exista cu cel mult P cifre 0 (zero) consecutive.
b) cate numere exista cu cel putin Q cifre 0 (zero) consecutive.

b ahol van benne egy olyan ahol q zero koveti egymast
*/

using namespace std;
const int nmax = 50;
int v[23];
int nrCifre, baza, p, q;
long long int rp = 0; 

bool valid_p(int k) {
	if (v[k] > 1) return false;
	// -- meg kell szamoljam a nullasokat
	if (v[k] == 1) return true;
	else {
		int i = k;
		for (; v[i] == 0 && i > 0; i--);
		return (k - i) <= p;
	}
}

void afisare() {
	int temp = 1;
	for (int i = 1; i <= nrCifre - 1; i++) {
		if (v[i] == 1) temp++;
		cout << v[i] << " ";
	}
	cout << endl;
	rp += pow(baza - 1, temp);
}


void bk_max(int k) {
	int i;
	for (i = 0; i <= 1; i++) {
		v[k] = i;
		if (valid_p(k)) {
			if (k == nrCifre - 1)     
				afisare();
			else            
				bk_max(k + 1);
		};
	}
}


bool solutie(int k) {
	if (k < nrCifre - 1) return false;
	// ha megvan az osszes szam akkor megnezzuk nva e eleg nullas
	int maxim = 0, next = 0;
	for (int i = 1; i <= nrCifre - 1; i++)
		if (v[i] == 0){
			next++;
			if (maxim < next) maxim = next;
		}
		else next = 0;
	return maxim >= q;
}
void bk_min(int k) {
	int i;
	for (i = 0; i <= 1; i++) {
		v[k] = i;
		if (k < nrCifre) {
			if (solutie(k))
				afisare();
			else
				bk_min(k + 1);
		}
	};
}


int main(){
	freopen("zero.in", "r", stdin);
	freopen("zero.out", "w", stdout);
	cin >> nrCifre >> baza >> p >> q;

	bk_max(1);
	printf("%lld\n", rp);

	rp = 0;
	
	bk_min(1);
	printf("%lld\n", rp);

	fclose(stdin);
	fclose(stdout);
	return 0;
}