Arti vs Mex-Mans
Arti vs Mex-Mans
У Артема была последовательность x из n (1 ≤ n ≤ 100) чисел, для которой выполнялось следующее свойство 1 ≤ L ≤ x1
≤ x2
≤ ... ≤ xn
≤ R ≤ 109
, а наименьшее общее кратное этих чисел делилось на a (1 ≤ a ≤ 109
). Но пришел Мансур и украл последовательность x. Артем очень расстроился, ведь он не помнит значения чисел своей последовательности. Он помнит только числа n, L, R и a. Он хочет восстановить последовательность. Для этого он решил сначала посчитать, а сколько вообще существует последовательностей, с такими же n, L, R и a. Помогите ему - напишите программу для решения этой задачи.
Входные данные
Единственная строка содержит четыре целых положительных числа, разделенных пробелами: n, L, R, a.
Выходные данные
Выведите единственное число, ответ на задачу. Так как ответ может быть очень большим, выведите его остаток от деления на 109
+ 7.
Пояснение
В первом тестовом примере подходящими последовательностями будут следующие:
{1, 6}, {2, 3}, {2, 6},
{3, 4}, {3, 6}, {4, 6},
{5, 6}, {6, 6}, {6, 7}
2 1 7 6
9
1 1 50 7
7