d,l,r,k = map(int,input().split())
mod = 10**9+7
ans = 0
depl = len(bin(l))-3
depr = len(bin(r))-3

fact = [1]*((1<<d)+1)
for i in range(2,(1<<d)+1):
    fact[i] = fact[i-1]*i%mod


ans = 0

for i in range(d+1):
    p = depl-i
    if p < 0:
        continue

    dif = k-i

    if dif < 0 or dif != depr-p:
        continue

    base = 1<<depl
    if i:
        base *= ((1<<depr-p) - (1<<depr-p)//2)
    else:
        base *= 1<<depr-p
    base %= mod
    for i in range(d):
        cand = 1<<i
        if i == depl:
            cand -= 1
        if i == depr:
            cand -= 1

        base *= fact[cand]
        base %= mod
    ans += base
    ans %= mod
print(ans)