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

int n,a,k,p;

int quick(int x,int l){
    int sum=1;
    for(int i=0;i<=15;i++){
        if(l>>i&1){
            sum*=x;
            sum%=p;
        } 
        x*=x;
        x%=p;
    }
    return sum;
}

int div(int m){
    if(m==1) return a;
    int sum=div(m/2);
    if(m&1) return (sum+sum*quick(a,m/2)%p+quick(a,m)%p)%p;
    else return (sum+sum*quick(a,m/2)%p)%p;
}
signed main()
{
    freopen("oeis.in","r",stdin);
    freopen("oeis.out","w",stdout);
    int ans=0,sum;
    cin>>n>>a>>k>>p;sum=a;
    if(k){
       for(int i=1;i<=n;i++){
        ans+=quick(i,k)*sum;
        ans%=p;
        sum*=a;
        sum%=p;
    }
    cout<<ans<<endl; 
    }else{
        cout<<div(n)%p<<endl;
    }
    
    return 0;
}