Артем проти Мансура

Артем мав послідовність x з n чисел, яка задовольняла умову: 1 ≤ L ≤ x[1] ≤ x[2] ≤ ... ≤ x[n] ≤ R ≤ 10^9, і найменше спільне кратне цих чисел було кратним a (1 ≤ a ≤ 10^9). Проте, Мансур викрав цю послідовність, і тепер Артем не може згадати її значення. Він пам'ятає лише числа n, L, R і a. Артем хоче відновити послідовність, тому вирішив спочатку визначити кількість можливих послідовностей з такими ж n, L, R і a. Допоможіть йому, написавши програму для розв'язання цієї задачі.

Вхідні дані

Єдиний рядок містить чотири цілі додатні числа, розділені пробілами: n, L, R, a.

Вихідні дані

Виведіть єдине число — кількість можливих послідовностей. Оскільки відповідь може бути дуже великою, виведіть її залишок від ділення на 10^9 + 7.

Приклади

Примітка

У першому тестовому прикладі можливими послідовностями є:

{1, 6}, {2, 3}, {2, 6},

{3, 4}, {3, 6}, {4, 6},

{5, 6}, {6, 6}, {6, 7}