#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

template <ll M>
struct modular {
    ll val;

    // n >= 0
    modular(const ll n) {
        if (n < M)
            val = n;
        else if (n < 2 * M)
            val = n - M;
        else
            val = n % M;
    }

    [[nodiscard]] modular operator +(const modular& rhs) const {
        return val + rhs.val;
    }

    [[nodiscard]] modular operator -(const modular& rhs) const {
        return val + M - rhs.val;
    }

    [[nodiscard]] modular operator *(const modular& rhs) const {
        return val * rhs.val;
    }

    // p >= 0
    [[nodiscard]] modular pow(const ll& p) const {
        if (p == 0)
            return 1;

        if (p % 2 == 0)
            return (*this * *this).pow(p / 2);
        else
            return *this * pow(p - 1);
    }

    [[nodiscard]] modular inv() const {
        return pow(M - 2);
    }

    [[nodiscard]] modular operator /(const modular& rhs) const {
        return *this * rhs.inv();
    }

    modular& operator +=(const modular& rhs) {
        return *this = *this + rhs;
    }

    modular& operator -=(const modular& rhs) {
        return *this = *this - rhs;
    }

    modular& operator *=(const modular& rhs) {
        return *this = *this * rhs;
    }

    modular& operator /=(const modular& rhs) {
        return *this = *this / rhs;
    }

    explicit operator ll() const {
        return val;
    }
};

template <ll M>
ostream& operator<<(ostream& os, const modular<M>& modular) {
    cout << modular.val;
    return os;
}

using mod = modular<1'000'000'007>;

ll n, m, l, r, k;

vector<mod> identity;

vector<mod> combine(vector<mod> const& a, vector<mod> const& b) {
    vector<mod> ret(m, 0);
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            int k = (i + j) % m;

            ret[k] += a[i] * b[j];
        }
    }

    return ret;
}

vector<mod> calc(int const n) {
    if (n == 1)
        return identity;
    else if (n % 2 == 1)
        return combine(calc(n - 1), identity);
    else {
        auto const half = calc(n / 2);
        return combine(half, half);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> l >> r >> k;

    identity.assign(m, 0);

    for (int i = 0; i < m; i++) {
        identity[i] += (r - i + m) / m;
        identity[i] -= (l - 1 - i + m) / m;
    }

    auto const ans = calc(n);

    cout << ans[k] << "\n";
}