#include <bits/stdc++.h>

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int MOD = 10000;
int A, B, N, K;

inline int add(int a, int b) {
    a += b;
    if(a >= MOD) {
        a -= MOD;
    }
    return a;
}

inline int mult(int a, int b) {
    return (1LL * a * b) % MOD;
}

inline int sub(int a, int b) {
    a -= b;
    if(0 > a) {
        a += MOD;
    }
    return a;
}

ii operator * (const ii &lhs, const ii &rhs) {
    ii ret = ii(add(mult(B, mult(lhs.second, rhs.second)), mult(lhs.first, rhs.first)), add(mult(lhs.first, rhs.second), mult(lhs.second, rhs.first)));
    return ret;
}

ii f_exp(ii p, int exp) {
    if(exp == 0) {
        return ii(1, 0);
    }
    else if(exp & 1) {
        return p * f_exp(p, exp - 1);
    }
    return f_exp(p * p, exp >> 1);
}

int main() {
    ios_base::sync_with_stdio(false);

    cin >> A >> B >> N >> K;

    ii p = f_exp(ii(A, 1), N);
    int a = p.first;
    a = mult(a, 2);

    if(N & 1) {
        if(A > sqrt(B)) {
            a = sub(a, 1);
        }
    }
    else {
        if(A * A != B) {
            a = sub(a, 1);
        }
    }

    string num = to_string(a);
    while(num.size() < 4) {
        num = "0" + num;
    }
    reverse(num.begin(), num.end());
    cout << num[K - 1] << '\n';

    return 0;
}