F. Джи, видишь?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время подготовки к ICPC команда «Jee You See» наткнулась на одну простую комбинаторную задачу. После большого количества вердиктов «Неправильный ответ» они решили сдаться и разбить выключить компьютер. Теперь они нуждаются в вашей помощи, чтобы дорешать задачу.

Вам даны 4 целых числа $$$n$$$, $$$l$$$, $$$r$$$ и $$$z$$$. Вычислите количество массивов $$$a$$$ длины $$$n$$$, состоящих из неотрицательных целых чисел таких, что:

Так как ответ может быть большим, выведите его по модулю $$$10^9+7$$$.

Входные данные

Единственная строка содержит четыре целых числа $$$n$$$, $$$l$$$, $$$r$$$, $$$z$$$ ($$$1 \le n \le 1000$$$, $$$1\le l\le r\le 10^{18}$$$, $$$1\le z\le 10^{18}$$$).

Выходные данные

Выведите количество подходящих массивов $$$a$$$ по модулю $$$10^9+7$$$.

Примеры
Входные данные
3 1 5 1
Выходные данные
13
Входные данные
4 1 3 2
Выходные данные
4
Входные данные
2 1 100000 15629
Выходные данные
49152
Входные данные
100 56 89 66
Выходные данные
981727503
Примечание

Следующие массивы подходят в первом примере:

  • $$$[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]$$$.