codeforces#P1670F. Jee, You See?

Jee, You See?

Description

During their training for the ICPC competitions, team "Jee You See" stumbled upon a very basic counting problem. After many "Wrong answer" verdicts, they finally decided to give up and destroy turn-off the PC. Now they want your help in up-solving the problem.

You are given 4 integers $n$, $l$, $r$, and $z$. Count the number of arrays $a$ of length $n$ containing non-negative integers such that:

  • $l\le a_1+a_2+\ldots+a_n\le r$, and
  • $a_1\oplus a_2 \oplus \ldots\oplus a_n=z$, where $\oplus$ denotes the bitwise XOR operation.

Since the answer can be large, print it modulo $10^9+7$.

The only line contains four integers $n$, $l$, $r$, $z$ ($1 \le n \le 1000$, $1\le l\le r\le 10^{18}$, $1\le z\le 10^{18}$).

Print the number of arrays $a$ satisfying all requirements modulo $10^9+7$.

Input

The only line contains four integers $n$, $l$, $r$, $z$ ($1 \le n \le 1000$, $1\le l\le r\le 10^{18}$, $1\le z\le 10^{18}$).

Output

Print the number of arrays $a$ satisfying all requirements modulo $10^9+7$.

Samples

3 1 5 1
13
4 1 3 2
4
2 1 100000 15629
49152
100 56 89 66
981727503

Note

The following arrays satisfy the conditions for the first sample:

  • $[1, 0, 0]$;
  • $[0, 1, 0]$;
  • $[3, 2, 0]$;
  • $[2, 3, 0]$;
  • $[0, 0, 1]$;
  • $[1, 1, 1]$;
  • $[2, 2, 1]$;
  • $[3, 0, 2]$;
  • $[2, 1, 2]$;
  • $[1, 2, 2]$;
  • $[0, 3, 2]$;
  • $[2, 0, 3]$;
  • $[0, 2, 3]$.

The following arrays satisfy the conditions for the second sample:

  • $[2, 0, 0, 0]$;
  • $[0, 2, 0, 0]$;
  • $[0, 0, 2, 0]$;
  • $[0, 0, 0, 2]$.