18740번 - Potato Shuffle 다국어

Marichka has a lot of potato in her basement. There are n bags with potato in a line. The i-th of them contains a_i potatoes.

Zenyk loves to shuffle those bags. During one shuffle operation he can grab two adjacent bags and swap their positions if the total number of potatoes in this two bags does not exceed number k. Zenyk can perform as many shuffle operations as he wishes.

Once Zenyk and Marichka wondered, what is the total number of bag permutations Zenyk can achieve. Two bag permutations are considered different if there is a position where two bags have different number of potatoes.

The first line contains two integers n (1 ≤ n ≤ 10⁵) and k (0 ≤ k ≤ 2 · 10⁹). The second line contains n integers a_i (1 ≤ a_i ≤ 10⁹).

Single integer — the number of different permutations modulo 10⁹ + 7.