#include <bits/stdc++.h>

using i64 = long long;

int power(int a, int b, int p) {
    int res = 1;
    for (; b; b /= 2, a = 1LL * a * a % p) {
        if (b % 2) {
            res = 1LL * res * a % p;
        }
    }
    return res;
}

int qint(int q, int n, int p) {
    auto rec = [&](auto self, int n) -> std::pair<int, int> {
        if (n == 0) {
            return {0, 1};
        }
        auto [x, y] = self(self, n / 2);
        x = 1LL * x * (1 + y) % p;
        y = 1LL * y * y % p;
        if (n % 2) {
            x = (x + y) % p;
            y = 1LL * y * q % p;
        }
        return {x, y};
    };
    return rec(rec, n).first;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int q, n, k, p;
    std::cin >> q >> n >> k >> p;
    
    int t = k / p;
    k -= t * p;
    n -= t * p;
    k = std::min(k, n - k);
    
    int ans = 1;
    for (int i = 1; i <= k; i++) {
        ans = 1LL * ans * qint(q, n - i + 1, p) % p;
        ans = 1LL * ans * power(qint(q, i, p), p - 2, p) % p;
    }
    std::cout << ans << "\n";
    
    return 0;
}