#include <iostream>

using namespace std;

long long n;
long long a;
long long k;
long long P;
long long res;

long long quick_pow (long long x, long long y) {
    long long ans = 1;
    while (y) {
        if (y & 1) {
            ans = ans * x % P;
        }
        x = x * x % P;
        y >>= 1;
    }
    return ans;
}

long long magic_cut_a (long long l, long long r) {
    if (l == r) {
        return a;
    }
    
    long long mid = (l + r) / 2;
    long long t = (magic_cut_a (l, mid) + magic_cut_a (mid + 1, r) * quick_pow (a, mid + 1 - l) % P) % P;
    return t;
}

int main () {
    
    freopen ("oeis.in", "r", stdin);
    freopen ("oeis.out", "w", stdout);
    
    cin >> n >> a >> k >> P;
    
    if (k == 0) {
        res = magic_cut_a (1, n);
    }
    else if (n <= 1000000) {
        for (int i = 1; i <= n; i++) {
            long long t = (quick_pow (i, k) * quick_pow (a, i)) % P;
            res = (res + t) % P;
        }
    }
    
    cout << res << endl;
    
    return 0;
}