Göydələn#11818

Göydələn

1 saniyə

128 meqabayt

Çox çətin

Beynəlxalq İnformatika Olimpiadası Yaponiya, Tsukuba şəhərində keçiriləcək. IOI-yə hazırlıq çərçivəsində biz Tsukuba-nın əsas küçəsində göydələnlər tikməyi planlaşdırırıq. Yeni bir görməli yer yaratmaq istədiyimiz üçün binalar aşağıdakı şərtlərə cavab verməlidir.

Biz əsas xətt boyunca bir düz xətt boyunca $n$ bina tikməyi planlaşdırırıq. Onların hündürlükləri $a_{1}, a_{2}, a_{3}, ..., a_{n}$ a_1, a_2, a_3, ..., a_n kimi verilir. Bütün hündürlüklər fərqlidir. Binanın yerləşmə qaydası hələ müəyyən olunmadığı üçün onları istənilən qaydada düzəldə bilərik. Binalar IOI üçün bəzədiləcəkdir. Lakin istifadə olunan materiallarla bağlı məhdudiyyətlərə görə qonşu binaların hündürlüklərinin fərqinin cəmi $L$ -dən çox olmamalıdır. Başqa sözlə, küçənin bir tərəfinə yerləşdirilən binaların hündürlüklərini $f_{1}, f_{2}, f_{3}, ..., f_{n}$ f_1, f_2, f_3, ..., f_n kimi təyin etsək, aşağıdakı ifadə yerinə yetirilməlidir:

∣ f_{1} - f_{2} ∣ + ∣ f_{2} - f_{3} ∣ + ... + ∣ f_{n - 1} - f_{n} ∣ \leq L

|f_1 - f_2| + |f_2 - f_3| + ... + |f_{n-1} - f_n| \le L

Burada $∣ x ∣$ ədədi dəyəri göstərir.

Belə tələblərə cavab verən bina silsilələrinin sayını neçə mümkündür?

Verilmiş binaların sayı $n$ , onların hündürlükləri və qonşu binaların hündürlük fərqlərinin cəmi üçün $L$ məhdudiyyətinə görə, binaların uyğun peşəkar surətini hesablamaq üçün bir proqram yazın. Cavab çox böyük ola bilər, buna görə cavabın $1000000007$ -ə bölünmə qalığını çıxışa verin.

Giriş

Aşağıdakı məlumatı standart girişdən oxuyun.

Birinci sətir iki tam ədəd $n$ və $L (1 \leq n \leq 100, 1 \leq L \leq 1000)$ L~(1 \le n \le 100, 1 \le L \le 1000) — binaların sayı və qonşu binaların hündürlük fərqlərinin cəmində üst həddini ehtiva edir.
İkinci sətir $n$ tam ədəd $a_{1}, a_{2}, a_{3}, ..., a_{n} (1 \leq a_{i} \leq 1000 (1 \leq i \leq n), a_{i} \neq = a_{j} (1 \leq i < j \leq n))$ a_1, a_2, a_3, ..., a_n~(1 \le a_i \le 1000~(1 \le i \le n), a_i \ne a_j~(1 \le i < j \le n)) — binaların hündürlüklərini ehtiva edir.

Çıxış

Bir ədəd çıxarın — binaların uyğun peşəkar surətinin sayının $1000000007$ -ə bölünmə qalığı.

Nümunələr

Nümunə 1

Nümunə 2

Qeyd

Altbölmə 1 [5 xal]: $n \leq 8$ n \le 8.

Altbölmə 2 [15 xal]: $n \leq 14, L \leq 100$ n \le 14, L \le 100.

Altbölmə 3 [80 xal]: Əlavə məhdudiyyət yoxdur.