d,l,r,k=map(int,input().split())
M=10**9+7
N=1<<d
fa=[1]
for i in range(1,N+1):
  fa+=[fa[-1]*i%M]
dl=len(bin(l))-3
dr=len(bin(r))-3
a=1
for i in range(d):
  a*=fa[1<<i]
  a%=M
if k-(dr-dl)>=0 and (k-(dr-dl))%2==0:
  dm=dl-(k-(dr-dl))//2
  if dm==dl:
    a*=pow(fa[1<<dr],M-2,M)
    a*=1<<dl
    a*=1<<(dr-dl)
    a*=fa[(1<<dl)-1]*fa[(1<<dr)-1]
  elif dl==dr:
    a*=pow(fa[1<<dl],M-2,M)
    a*=1<<dm
    a*=2
    a*=1<<(dl-dm-1)
    a*=1<<(dl-dm-1)
    a*=fa[(1<<dl)-2]
  else:
    a*=pow(fa[1<<dl],M-2,M)*pow(fa[1<<dr],M-2,M)
    a*=1<<dm
    a*=2
    a*=1<<(dl-dm-1)
    a*=1<<(dr-dm-1)
    a*=fa[(1<<dl)-1]*fa[(1<<dr)-1]
else:
  a=0
print(a%M)