//Author: stdout 
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define debug(x) cerr<<#x<<" = "<<x<<"\n";
#define lowbit(x) ((x)&-(x))
const int inf=0x3f3f3f3f;
const double eps=1e-9;
//const double pi=acos(-1.0); 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	ull x,y,e=0,a,b;
	cin>>x>>y>>a>>b;
	while(x*(a-1)<b&&x*a<y) x*=a,++e;
	e+=(y-x-1)/b;
	cout<<e<<"\n";
	return 0;
} 
#include "bits/stdc++.h"
using namespace std;
#define int               long long
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll

template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.fr>>a.sc;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.fr<<" "<<a.sc;return out;}
template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}

const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;

const int N=19;

int n,m;
int dp[N][1<<N];

vector<pii> v[N];

int calc(int p,int mask){
	int &ans = dp[p][mask];
	if(ans != -1){
		return ans;
	}
	ans = 0;
	
	for(auto x:v[p]){
		int y = x.fr, z = x.sc;
		int cnt = mask % (1 << y);
		cnt = ppc(cnt);
		if(cnt > z){
			ans = 0;
			return ans;
		}
	}
	
	if(p == n){
		return ans = 1;
	}
	
	rep(i,0,n){
		if(mask >> i & 1) continue;
		ans += calc(p+1,mask|(1<<i));
	}
	return ans;
}

void solve(){
	mem1(dp);
	cin >> n >> m;
	rep(i,0,m){
		int x,y,z;
		cin >> x >> y >> z;
		
		v[x].pb({y,z});
	}
	cout << calc(0,0);
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	#ifdef SIEVE
		sieve();
	#endif
	#ifdef NCR
		init();
	#endif
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}
