#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
ll n,a,k,p,ans=0;
ll fpow(ll x,ll n){
    if(n==0) return 1;
    else if(n==1) return x%p;
    else{
        ll mid=n/2;
        ll t=fpow(x,mid)%p;
        if(n%2==0) return t%p*t%p;
        else return t%p*t%p*x%p;
    }
}
int main()
{
    freopen("oeis.in","r",stdin);
    freopen("oeis.out","w",stdout);
    
    cin>>n>>a>>k>>p;
    if(n<=1e6){
        ll po=a;
        for(int i=1;i<=n;i++){
            ll t=fpow(i,k)%p;
            ans=(ans+t%p*po%p)%p;
            po*=a;
            po%=p;
        }
    }else if(k==0){
        ans=a*(1-fpow(a,n))/(1-a)%p;
    }else if(a==1){
        for(int i=1;i<=n;i++){
            ans=(ans+fpow(i,k))%p;
        }
    }
    cout<<ans<<endl;
    return 0;
}