#include <iostream>
#include <math.h>
#include <cmath>

int main() {
    int a, b, c, k;
    std::cin >> a;
    std::cin >> b;
    std::cin >> k;
    std::cin >> c;

    /*unsigned long long i = 0;
    unsigned long aa = 0;

    while (true) {
        i += 64;
        aa++;
        if (i >= k) {
            break;
        }
    }

    unsigned long long bits[aa] {0};
    unsigned long long occurences = 0;
    while (true) {
        int selectField = 0;
        bool done = false;
        while (true) {
            if (bits[selectField] == UINT64_MAX) {
                bits[selectField] = 0;
                selectField++;
            } else {
                break;
            }
            if (selectField >= aa) {
                done = true;
                break;
            }
        }
        if (done) {
            break;
        }
        bits[selectField]++;
        for (int u = 0; u < aa; u++) {
            for (int z = 0; z < 64; z++) {
                if (bits[selectField] & (1 << z)) {
                    occurences++;
                }
            }
        }
    }

    std::cout << occurences;*/
    /*unsigned long long x = pow(2, k);
    x = x * k;
    x = x / 2;
    x = x % 1000000007;
    std::cout << x << std::endl;*/
    char bits[k];
    for (int i = 0; i < k; i++) {
        bits[i] = 0;
    }
    int start = 0;
    bool done = false;
    unsigned long long count = 0;
    while (true) {
        start = 0;
        while (true) {
            if (bits[start] == 1) {
                bits[start] = 0;
                start++;
            } else {
                break;
            }
            if (start >= k) {
                done = true;
                break;
            }
        }
        if (done) break;
        bits[start] = 1;
        /*for (int i = 0; i < k; i++) {
            printf("%s", bits[k - i - 1] == 1 ? "1" : "0");
        }
        printf("\n");*/
        for (int i = 0; i < k; i++) {
            if (bits[i] == 1) {
                count++;
                if (count >= 1000000007) {
                    count = count % 1000000007;
                }
            }
        }
    }

    std::cout << count << std::endl;

    return 0;
}