import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; class Main { public static void main(String[] args) { new Main().run(); } final long M=(long)1e9+7; long factorial(long n) { long ret=1; for(int i=1;i<=n;++i)ret=ret*i%M; return ret; } long pow(long a,long n) { return n==0?1:((n%2==1?a:1)*pow(a*a%M,n/2))%M; } long inv(long a) { return pow(a,M-2); } void run() { Scanner sc=new Scanner(System.in); int d=sc.nextInt(); int l=sc.nextInt(); int r=sc.nextInt(); int depth_left=Integer.numberOfTrailingZeros(Integer.highestOneBit(l))+1; int depth_right=Integer.numberOfTrailingZeros(Integer.highestOneBit(r))+1; int k=sc.nextInt(); int diff=depth_right-depth_left; if(diff>k||(k-diff)%2==1||(k-diff)>(depth_left-1)*2) { System.out.println(0); return; } long ans=1; for(int i=1;i<=d;++i) { ans=ans*factorial(1<<(i-1))%M; } long w=1L<<(depth_left-1); if(depth_left!=depth_right) { ans=ans*inv(w)%M*((k-diff)==0?1:(1L<<((k-diff)/2-1)))%M; }else { ans=ans*inv(w-1)%M*((k-diff)==0?1:(1L<<((k-diff)/2-1)))%M; } System.out.println(ans); } void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));} }