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}