#include<iostream>
using namespace std;
typedef long long ll;

ll n, a, k, P;
ll S[2005][2005], C[2005];

ll qpow(ll x, ll y){
	ll res = 1; x %= P;
	for(;y;y >>= 1,x = x * x % P){
	    if(y & 1){
	        res = res * x % P;
        }
    }
	return res;
}
ll inv(ll x){
	return qpow(x, P - 2);
}

int main(){
    freopen("oeis.in", "r", stdin);
    freopen("oeis.out", "w", stdout);
    cin >> n >> a >> k >> P;
	if(n <= 1000000){
		ll ans = 0;
		for(int i = 1;i <= n;i ++) ans = (ans + qpow(i, k) * qpow(a, i)) % P;
		cout << ans << "\n";
		return 0;
	}
	if(k == 0){
		if(a % P == 1) cout << n % P << "\n";
		else cout << (a % P * (qpow(a, n) - 1 + P) % P * inv((a - 1 % P + P) % P)) % P << "\n";
		return 0;
	}
	if(a % P == 1){
		S[0][0] = 1;
		for(int i = 1;i <= k;i ++)
		    for(int j = 1;j <= i;j ++)
		        S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j]) % P;
		C[0] = 1;
		for(int j = 1;j <= k + 1;j ++) C[j] = C[j - 1] * ((n + 1 - j + 1) % P) % P * inv(j) % P;
		ll ans = 0, fac = 1;
		for(int j = 0;j <= k;j ++){
			ans = (ans + S[k][j] * fac % P * C[j + 1]) % P;
			fac = fac * (j + 1) % P;
		}
		cout << ans << "\n";
		return 0;
	}
	return 0;
}