У Артема была последовательность 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}