Задача CUBES

Измежду играчките си, Октавия има N кубчета с еднакви размери. Кубчетата може да се различават по своето тегло, като е възможно две кубчета да имат еднакво тегло. Октавия много обича да подрежда кубчетата си в дълга редица и след много часове прекарани в игра, започна да се чуди по колко различни начина може да подреди редицата от кубчета.

Редицата от кубчета се представя като последователност от N цели числа, всяко от които съответства на теглото на поредното кубче в реда, в който се намират кубчетата първоначално. Октавия може да вдигне две съседни кубчета и да ги размени тогава, когато сумата от теглата им не надвишава цялото число K. Октавия може да прилага такава размяна на съседни кубчета, със сума на теглата не по-голяма от К, безброй много пъти. Две редици от кубчета са различни, когато редиците от теглата им са различни.

Нека вземам за пример следния случай с 4 кубчета с тегла [1, 2, 1, 3] и К = 3.

В този случай за възможни 3 различни подредби. Първата подредба е първоначалната: [1, 2, 1, 3].

За да получим втората подредба, може да разменим кубчетата на позиции 2 и 3 в първоначалната подредба и да получим подредбата [1, 1, 2, 3]. Забележете, че не може да разменим кубчета 1 и 3 в началната подредба, защото не са съседни. Също така не може да разменим кубчета 3 и 4, защото сумата от теглата им е 4, която надвишава K = 3.

Може да получим последната подредба като разменим кубчета на позиции 1 и 2 в първоначалната подредба и получим: [2, 1, 1, 3].

Забележете, че при тази начална подредба, при К = 1, има само една редица; при К = 2, също има 1 редица; при К = 4, има 6 редици, и при К = 5 има 12 редици.


Вход
От първия ред на стандартния вход се въвеждат две числа: N – броя на кубчетата и K – максималната сума от тегла на две съседни кубчета, които могат да бъдат разменени. От втория ред се въвеждат N цели положителни числа w_i, които съответстват на теглата на кубчетата в началната редица.

Изход
На стандартния изход изведете броя на възможните подредби по модул 1’000’000’007.

Ограничения
1 ≤ N ≤ 3 * 10^5
1 ≤ K, w_i ≤ 10^9
