#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_ON			1										// 汎用フラグ - ON
#define D_OFF			0										// 汎用フラグ - OFF
#define D_MOD			1000000007								// 除数(10の9乗+7)
#define D_SIZE_MAX		35										// 最大サイズ
#define D_FRD_MAX		15										// 最大フレンズ数

// 内部構造体 - フレンズ情報
typedef struct Frd {
	char mc1Name[16];											// 名称
	int miX, miY;												// 位置
} Frd;

// 内部変数
static FILE *szpFpI;											// 入力
static int siW, siH;											// 幅・高さ
static Frd sz1Frd[D_FRD_MAX];									// フレンズ
static int siFCnt;												// フレンズ数
static int siJCnt;												// ジャパリまん数
static long long sl2PCnt[D_SIZE_MAX][D_SIZE_MAX];				// パターン数
static long long slMax;											// 最大パターン数
static Frd *szp1MaxFrd[D_FRD_MAX];								// 最大パターン時のフレンズ
static int siMaxFCnt;											// 最大パターン時のフレンズ数

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// 出力
int
fOut(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// パターン数 - セット
int
fSetPCnt(
	int *pipSel					// <I> 選択
)
{
	int i, j;

	// 初期化
	memset(sl2PCnt, 0, sizeof(sl2PCnt));

	// フレンズ
	int liFCnt = 0;
	for (i = 0; i < siFCnt; i++) {
		if (pipSel[i] == D_ON) {
			liFCnt++;
		}
		else {
			sl2PCnt[sz1Frd[i].miX][sz1Frd[i].miY] = -1;
		}
	}
	if (liFCnt > siJCnt) {
		return 0;
	}

	// １行目・１列目
	sl2PCnt[0][0] = 1;
	for (i = 1; i <= siW; i++) {
		if (sl2PCnt[i][0] < 0) {
			sl2PCnt[i][0] = 0;
		}
		else {
			sl2PCnt[i][0] += sl2PCnt[i - 1][0];
		}
	}
	for (i = 1; i <= siH; i++) {
		if (sl2PCnt[0][i] < 0) {
			sl2PCnt[0][i] = 0;
		}
		else {
			sl2PCnt[0][i] += sl2PCnt[0][i - 1];
		}
	}

	// ２行目・２列目以降
	for (i = 1; i <= siW; i++) {
		for (j = 1; j <= siH; j++) {
			if (sl2PCnt[i][j] < 0) {
				sl2PCnt[i][j] = 0;
			}
			else {
				sl2PCnt[i][j] = sl2PCnt[i - 1][j] + sl2PCnt[i][j - 1];
			}
		}
	}

	// 最大パターン数
	if (slMax >= sl2PCnt[siW][siH]) {
		return 0;
	}
	slMax = sl2PCnt[siW][siH];

	// 最大パターン時のフレンズ
	siMaxFCnt = 0;
	for (i = 0; i < siFCnt; i++) {
		if (pipSel[i] == D_ON) {
			szp1MaxFrd[siMaxFCnt] = &sz1Frd[i];
			siMaxFCnt++;
		}
	}

	return 0;
}

// フレンズ - 選択
int
fSelFrd(
	int piFNo					// <I> フレンズ 0～
	, int *pipSel				// <I> 選択
)
{
	// 選択中
	if (piFNo < siFCnt) {

		// 選択
		pipSel[piFNo] = D_ON;
		fSelFrd(piFNo + 1, pipSel);

		// 選択なし
		pipSel[piFNo] = D_OFF;
		fSelFrd(piFNo + 1, pipSel);

		return 0;
	}

	// パターン数 - セット
	fSetPCnt(pipSel);

	return 0;
}

// 実行メイン
int
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// 幅・高さ・フレンズ数・ジャパリまん数 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d%d%d", &siW, &siH, &siFCnt, &siJCnt);

	// フレンズ - 取得
	for (i = 0; i < siFCnt; i++) {
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d%s", &sz1Frd[i].miX, &sz1Frd[i].miY, sz1Frd[i].mc1Name);
	}

	// フレンズ - 選択
	int li1Sel[D_FRD_MAX];
	fSelFrd(0, li1Sel);

	// 出力 - 最大パターン数
	sprintf(lc1Buf, "%d\n", (int)(slMax % (long long)D_MOD));
	fOut(lc1Buf);

	// 出力 - 最大パターン時のフレンズ
	for (i = 0; i < siMaxFCnt; i++) {
		sprintf(lc1Buf, "%s\n", szp1MaxFrd[i]->mc1Name);
		fOut(lc1Buf);
	}

	return 0;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// データ - 初期化
	slMax = 0;													// 最大パターン数
	siMaxFCnt = 0;												// 最大パターン時のフレンズ数

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}