import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int d = Integer.parseInt(sa[0]); int l = Integer.parseInt(sa[1]); int r = Integer.parseInt(sa[2]); int k = Integer.parseInt(sa[3]); br.close(); int dl = 1; for (int i = 1; i <= d; i++) { if ((1 << i) > l) { dl = i; break; } } int dr = 1; for (int i = 1; i <= d; i++) { if ((1 << i) > r) { dr = i; break; } } if (dr - dl <= k && k <= (dl + dr - 2) && (dr - dl) % 2 == k % 2) { int mod = 1000000007; int end = 1 << (d - 1); long[] p = new long[end + 1]; p[0] = 1; for (int i = 1; i < p.length; i++) { p[i] = p[i - 1] * i % mod; } int k2 = k - (dr - dl); k2 /= 2; long ans = 1; for (int i = 0; i < d; i++) { if (dl > 1 && i + 1 == dr) { ans *= 1 << i; ans %= mod; ans *= 1 << (k2 - 1); ans %= mod; ans *= p[(1 << i) - 2]; } else { ans *= p[1 << i]; } ans %= mod; } System.out.println(ans); } else { System.out.println(0); } } }