#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n,a,k,mod;
ll ans;

ll mpow(ll aa,ll bb){
	ll res=1;
	while (bb){
		if (bb&1) res=res*aa%mod;
		aa=aa*aa%mod;
		bb>>=1;
	}
	return res;
}

void solve1(){
	for (int i=1;i<=n;i++){
		ans+=mpow(i,k)*mpow(a,i)%mod;
		ans%=mod;
	}
	cout<<ans<<'\n';
}

void dfs(ll l,ll r){
	if (r-l>=5e5){
		ll mid=(l+r)/2;
		dfs(l,mid);
		dfs(mid+1,r);
	}else{
		ll res=0;
		for (int i=0;i<=r-l;i++){
			res+=mpow(a,i);
			res%=mod;
		}
		ans+=mpow(a,l)*res%mod;
		ans%=mod;
	}
}

void solve2(){
	dfs(1,n);
	cout<<ans<<'\n';
}

void solve3(){
	solve1();
}

int main(){
	freopen("oeis.in","r",stdin);
	freopen("oeis.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>a>>k>>mod;
	if (n<=1000000){
		solve1();
	}else if (k==0){
		solve2();
	}else if (a==1){
		solve3();
	}else if (k<=100){
		solve1();
	}
	return 0;
}