Artem Mənsura qarşı

Artemin x ardıcıllığı var idi, burada n (1 ≤ n ≤ 100) ədəd var idi və bu ardıcıllıq aşağıdakı xüsusiyyətə malik idi: 1 ≤ L ≤ x[1] ≤ x[2] ≤ ... ≤ x[n] ≤ R ≤ 10^9, və bu ədədlərin ən kiçik ortaq böləni a-ya bölünürdü (1 ≤ a ≤ 10^9). Lakin Mansur gəlib x ardıcıllığını oğurladı. Artem çox kədərləndi, çünki ardıcıllığının ədədlərini xatırlamır. O yalnız n, L, R və a ədədlərini xatırlayır. O, ardıcıllığı bərpa etmək istəyir. Bunun üçün əvvəlcə belə n, L, R və a ilə neçə ardıcıllığın mövcud olduğunu hesablamaq qərarına gəldi. Ona kömək edin - bu məsələnin həlli üçün proqram yazın.

Giriş məlumatları

Yeganə sətir dörd müsbət tam ədədi ehtiva edir, boşluqlarla ayrılmış: n, L, R, a.

Çıxış məlumatları

Məsələnin cavabını tək bir ədəd kimi çıxarın. Cavab çox böyük ola biləcəyi üçün onu 10^9 + 7-yə bölünmənin qalığı kimi çıxarın.

İzah

Birinci test nümunəsində uyğun ardıcıllıqlar aşağıdakılar olacaq:

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

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

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