Мансур Кутыбаев


Есеп №1. У Артема была последовательность $x$ из $1 \le N \le 100$ чисел, для которой выполнялось следующее свойство $1 \le L \le x_1 \le x_2 \le \ldots \le x_N \le R \le 10^9$, а наименьшее общее кратное этих чисел делилось на $1 \le A \le 10^9$. Но пришел Мансур и украл последовательность $x$. Артем очень расстроился, ведь он не помнит значения чисел своей последовательности. Он помнит только числа $N$, $L$, $R$ и $A$. Он хочет восстановить последовательность. Для этого он решил сначала посчитать, а сколько вообще существует последовательностей, с такими же $N$, $L$, $R$ и $A$. Помогите ему, --- напишите программу для решения этой задачи.
Входные данные:
Единственная строка входных данных содержит четыре целых положительных числа, разделенных пробелами: $N$, $L$, $R$, $A$.
Выходные данные:
Выведите единственное число, ответ на задачу. Так как ответ может быть очень большим, выведите его остаток от деления на $10^9 + 7$.
Примеры:
1.Вход: 
2 1 7 6
Ответ: 
9
2.Вход: 
1 1 50 7
Ответ: 
7
В первом тестовом примере подходящими последовательностями будут следующие::
${ 1, 6}$, ${ 2, 3}$, ${ 2, 6}$
${ 3, 4}$, ${ 3, 6}$, ${ 4, 6}$
${ 5, 6}$, ${ 6, 6}$, ${ 6, 7}$
Оценивание:
Данная задача содержит 5 подзадачи:
$1 \le N \le 2$, $1 \le A,L,R \le 100$. Оценивается в $6$ баллов.
$1 \le N \le 2$, $1 \le A,L,R \le 1000$. Оценивается в $11$ баллов.
$1 \le N \le 10$, $1 \le A,L,R \le 1000$. Оценивается в $15$ баллов.
$1 \le N \le 10$, $1 \le A,L,R \le 10^6$. Оценивается в $21$ балл.
$1 \le N \le 100$, $1 \le A,L,R \le 10^9$. Оценивается в $47$ баллов.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих. ( Мансур Кутыбаев )
комментарий/решение олимпиада