# 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].