Jee, You See? solution codeforces

Jee, You See? solution codeforces – 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.

Jee, You See? solution codeforces

You are given 4 integers nnllrr, and zz. Count the number of arrays aa of length nn containing non-negative integers such that:

  • la1+a2++anrl≤a1+a2+…+an≤r, and
  • a1a2an=za1⊕a2⊕…⊕an=z, where  denotes the bitwise XOR operation.

Since the answer can be large, print it modulo 109+7109+7.

Input

The only line contains four integers nnllrrzz (1n10001≤n≤10001lr10181≤l≤r≤10181z10181≤z≤1018).

Output

Print the number of arrays aa satisfying all requirements modulo 109+7109+7.

Jee, You See? solution codeforces

Examples
input

Copy
3 1 5 1
output

Copy
13
input

Copy
4 1 3 2
output

Copy
4

Jee, You See? solution codeforces

input

Copy
2 1 100000 15629
output

Copy
49152
input

Copy
100 56 89 66
output

Copy
981727503

Jee, You See? solution codeforces

The following arrays satisfy the conditions for the first sample:

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

The following arrays satisfy the conditions for the second sample:

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

 

For Solution

Click here

Leave a Comment