#include<bits/stdc++.h>
using namespace std;
long long n,a,k,M,as,ps[2009],s,xx,yy;
inline long long pw(long long x,long long y){
    long long ss=1;
    while(y){
        if(y&1) ss=ss*x%M;
        x=x*x%M;
        y>>=1;
    }
    return ss;
}
long long df(long long x,long long y){
    if(y==0) return 1;
    if(y==1) return x+1;
    long long ss=df(x,(y-1)/2);
    ss=(ss+ss*pw(x,(y-1)/2+1))%M;
    if(y&1) return ss;
    return (ss+pw(x,y))%M;
}
void exgcd(long long a,long long b,long long &x,long long &y){
    if(!b){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    long long yy=y;
    y=(x-(a/b)*y)%M;
    x=yy;
    return;
}
int main(){
    freopen("oeis.in","r",stdin);
    freopen("oeis.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>a>>k>>M;
    a%=M; 
    if(n<=1000000){
        for(long long i=1;i<=n;i++){
            as=(as+pw(i,k)*pw(a,i))%M;
        }
        cout<<as;
        return 0;
    }
    if(!k){
        cout<<(df(a,n)-1+M)%M;
        return 0;
    }
    if(a==1){
        for(int i=1;i<=k+3;i++){
            ps[i]=(ps[i-1]+pw(i,k))%M;
        }
        for(long long i=1;i<=k+3;i++){
            long long s1=1,s2=1;
            for(long long j=1;j<=k+3;j++){
                if(i==j) continue;
                s1=s1*(i-j)%M;
                s2=s2*(n-j)%M;
            }
            s1=(s1%M+M)%M;
            s2=(s2%M+M)%M;
            exgcd(s1,M,xx,yy);
            xx=(xx%M+M)%M;
            s=(s+s2*xx%M*ps[i])%M;
        }
        s=(s%M+M)%M;
        cout<<s;
        return 0;
    }
    return 0;
}