#include<bits/stdc++.h>
#define ll long long
#define N 2001
using namespace std;
ll n,a,k,p,ans,sum[5000001],cnt;
map<ll,ll> mp;
ll qpow(ll x,ll y){
    ll res=1;
    while(y>0){
        if(y%2==1) res=res*x%p;
        y/=2;
        x=x*x%p;
    }
    return res;
}
int main(){
    freopen("oeis.in","r",stdin);
    freopen("oeis.out","w",stdout);
    cin>>n>>a>>k>>p;
    if(n<=1000000){
        for(int i=1;i<=n;i++) ans=(ans+qpow(i,k)%p*qpow(a,i)%p)%p;
        cout<<ans<<endl;
    }else if(k==0){
        while(++cnt){
            if(cnt>n){
                ans=sum[cnt-1];
                break;
            }
            ll fz=qpow(a,cnt);
            if(mp[fz]==1){
                ans=(sum[cnt-1]*(n/cnt)%p+sum[n%cnt])%p;
                break;
            }
            mp[fz]=1;
            sum[cnt]=(sum[cnt-1]+fz)%p;
        }
        cout<<ans<<endl;
    }else if(a==1){
        for(int i=1;i<min(n+1,p);i++) ans+=qpow(i,k);
        cout<<ans<<endl;
    }else cout<<"You did it!"<<endl;
    return 0;
}