Республиканская олимпиада по информатике, 2015 год, 10-11 класс

Задача D. Arti vs Mex-Mans

У Артема была последовательность $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$ баллов.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих. ( Мансур Кутыбаев )