Во время подготовки к ICPC команда «Jee You See» наткнулась на одну простую комбинаторную задачу. После большого количества вердиктов «Неправильный ответ» они решили сдаться и разбить выключить компьютер. Теперь они нуждаются в вашей помощи, чтобы дорешать задачу.
Вам даны 4 целых числа \(n\), \(l\), \(r\) и \(z\). Вычислите количество массивов \(a\) длины \(n\), состоящих из неотрицательных целых чисел таких, что:
- \(l\le a_1+a_2+\ldots+a_n\le r\), а также
- \(a_1\oplus a_2 \oplus \ldots\oplus a_n=z\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Так как ответ может быть большим, выведите его по модулю \(10^9+7\).
Выходные данные
Выведите количество подходящих массивов \(a\) по модулю \(10^9+7\).
Примечание
Следующие массивы подходят в первом примере:
- \([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]\).
Следующие массивы подходят во втором примере:
- \([2, 0, 0, 0]\);
- \([0, 2, 0, 0]\);
- \([0, 0, 2, 0]\);
- \([0, 0, 0, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1 5 1
|
13
|
|
2
|
4 1 3 2
|
4
|
|
3
|
2 1 100000 15629
|
49152
|
|
4
|
100 56 89 66
|
981727503
|