## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Jee, You See? Codeforces Solution | Codeforces Problem Solution 2022

F. Jee, You See?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

Prof. Slim Codeforces Solution | Codeforces Problem Solution 2022

Dorms War Codeforces Solution | Codeforces Problem Solution 2022

Where is the Pizza? Codeforces Solution | Codeforces Problem Solution 2022

Very Suspicious Codeforces Solution | Codeforces Problem Solution 2022

Hemose on the Tree Codeforces Solution | Codeforces Problem Solution 2022

Jee, You See? Codeforces Solution | Codeforces Problem Solution 2022

• $l\le {a}_{1}+{a}_{2}+\dots +{a}_{n}\le r$, and
• ${a}_{1}\oplus {a}_{2}\oplus \dots \oplus {a}_{n}=z$, where $\oplus$ denotes the bitwise XOR operation.

Since the answer can be large, print it 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$.