d, l, r, k = map(int, input().split())
mod = 10**9 + 7
depthl = 0
depthr = 0
for i in range(30):
    if 2**i <= l < 2**(i+1):
        depthl = i+1

for i in range(30):
    if 2**i <= r < 2**(i+1):
        depthr = i+1
ans = 0
power = [1 for i in range(10**6*2)]
for i in range(1, 10**6+10**5):
    power[i] = power[i-1]*i
    power[i] %= mod

for i in range(1, d+1):
    # lcaの高さを固定
    lca = i
    res = 2*pow(2, lca-1, mod)
    if depthl+depthr-2*lca != k:
        continue
    if depthl < lca:
        continue
    if lca < depthl:
        res = res*pow(2, depthl-lca-1, mod)*pow(2, depthr-lca-1, mod)
        D = {depth: 2**(depth-1) for depth in range(1, d+1)}
        D[depthr] -= 1
        D[depthl] -= 1
        D[lca] -= 1
        for depth in D.keys():
            res *= power[D[depth]]
            res %= mod
    elif lca == depthl:
        res *= pow(2, depthr-lca-1, mod)
        D = {depth: 2**(depth-1) for depth in range(1, d+1)}
        D[depthr] -= 1
        D[lca] -= 1
        for depth in D.keys():
            res *= power[D[depth]]
            res %= mod
    ans += res
    ans %= mod
print(ans%mod)