Potato Shuffle

Time limit1sMemory limit512 MB

Summary

Count the distinct bag arrangements reachable by swapping adjacent bags whose potato total is at most k, modulo 1000000007.

Level: Medium7 of 10
Topics: Array, Combinatorics, Sorting
Solved: No attempts yet

Problem

Marichka keeps a lot of potatoes in her basement. There are n bags of potatoes in a line, and the i-th bag contains a_i potatoes.

Zenyk likes to shuffle the bags. In one shuffle operation, he picks two adjacent bags and swaps their positions, but only if the total number of potatoes in those two bags does not exceed k. Zenyk can perform as many shuffle operations as he wants.

Marichka and Zenyk wondered how many different bag arrangements Zenyk can reach. Two arrangements are considered different if some position holds bags with different numbers of potatoes. Count the arrangements Zenyk can achieve.

Input

The first line contains two integers n and k ( $1 \le n \le 10^5$ , $0 \le k \le 2 \cdot 10^9$ ).

The second line contains n integers a_i ( $1 \le a_i \le 10^9$ ).

Output

Print one integer, the number of different arrangements modulo $10^9 + 7$ .

Examples2

Example 1
Input
```
3 7
5 2 4
```
Expected output
```
3
```
Example 2
Input
```
5 4
1 2 3 2 1
```
Expected output
```
10
```