#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int, int>;
#define rep(i,m,n) for(int (i)=(m);(i)<(n);++(i))
#define rrep(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr ll INF = 1LL << 60;
constexpr ll mod = 100000; //(ll)1e9 + 7;
constexpr double PI = 3.1415926535897932;

template<class T>inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T>inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
inline void init() {
    cin.tie(nullptr); cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
}

inline int popcount(ll n) {
    n = (n & 0x5555555555555555) + (n >> 1 & 0x5555555555555555);
    n = (n & 0x3333333333333333) + (n >> 2 & 0x3333333333333333);
    n = (n & 0x0f0f0f0f0f0f0f0f) + (n >> 4 & 0x0f0f0f0f0f0f0f0f);
    n = (n & 0x00ff00ff00ff00ff) + (n >> 8 & 0x00ff00ff00ff00ff);
    n = (n & 0x0000ffff0000ffff) + (n >> 16 & 0x0000ffff0000ffff);
    n = (n & 0x00000000ffffffff) + (n >> 32 & 0x00000000ffffffff);
    return n;
}

int dx[] = { 1,0,-1,0,1,-1,-1,1 };
int dy[] = { 0,1,0,-1,1,-1,1,-1 };

int H, W, A, B;
vector<vector<bool>>v;
int dfs(int cnt = 0) {
    if (cnt == A) return 1;
    int res = 0;
    rep(i, 0, H) {
        rep(j, 0, W) {
            if (v[i][j])continue;
            
            rep(k, 0, 2) {
                int x = j + dx[k], y = i + dy[k];
                if (out(y, x, H, W))continue;
                if (!v[y][x]) {
                    v[y][x] = true;
                    v[i][j] = true;
                    res += dfs(cnt + 1);
                    v[y][x] = false;
                    v[i][j] = false;
                }
            }
            return res;
        }
    }
    
}
int main() {
    init();

    cin >> H >> W >> A >> B;
    int _n = H * W, ans = 0;
    for (int bit = 0;bit < (1 << _n);++bit) {
        vector<vector<bool>>vec(H, vector<bool>(W, false));
        if (popcount(bit) != B)continue;
        rep(i, 0, _n) {
            if ((bit >> i) & 1)vec[i / W][i % W] = true;
        }
        v = vec;
        ans += dfs();
    }
    cout << ans << "\n";

    return 0;
}
#include<bits/stdc++.h>
using namespace std;
bool f1;
#define LL long long
#define db double
#define Max(a,b) ((a)<(b))&&((a)=(b))
#define Min(a,b) ((a)>(b))&&((a)=(b))
inline int rd() {
	int res=0;
	char ch;
	while(ch=getchar(),ch<48||ch>57);
	do res=(res<<1)+(res<<3)+(ch^48);
	while(ch=getchar(),ch>47&&ch<58);
	return res;
}
const int M=1<<18;
int n,m;
LL f[M];
struct info {
	int y,z;
};
int Sz[M];
vector<info>Q[20];
int X[M],Y[M],Z[M],sum[20];
bool f2;
int main() {
//	printf("%lf\n",(&f2-&f1)/1024.0/1024.0);
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	n=rd(),m=rd();
	for(int i=1; i<=m; ++i) {
		X[i]=rd(),Y[i]=rd(),Z[i]=rd();
		Q[X[i]].push_back((info)<%Y[i],Z[i]%>);
	}
	int t=1<<n;
	f[0]=1;
	for(int i=1; i<t;++i) {
		Sz[i]=Sz[i^(i&-i)]+1;
		memset(sum,0,sizeof sum);
		for(int j=0; j<n; ++j)if(i&(1<<j))f[i]+=f[i^(1<<j)],sum[j+1]++;
		for(int j=1; j<=n; ++j)sum[j]+=sum[j-1];
		for(int j=0; j<Q[Sz[i]].size(); ++j) {
			int yy=Q[Sz[i]][j].y,zz=Q[Sz[i]][j].z;
			if(sum[yy]>zz){f[i]=0;break;}
		}
	}
	printf("%lld",f[t-1]);
	return 0;
}
