Во время подготовки к 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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач