# Potato Shuffle

*Limits: 2 sec., 256 MiB*

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.

# Input

The first line contains two integers \(N\) and \(K\). The second line contains \(N\) integers \(A_i\).

# Output

Single integer — the number of different permutations mudulo \(10^9 + 7\).

# Constraints

\(1 \le N \le 10^5\),

\(0 \le K \le 2 \cdot 10^9\),

\(1 \le A_i \le 10^9\).

# Samples

Input (stdin) | Output (stdout) |
---|---|

3 7 5 2 4 | 3 |

Input (stdin) | Output (stdout) |
---|---|

5 4 1 2 3 2 1 | 10 |

# Notes

In the first sample possible permutations are: (5, 2, 4), (2, 5, 4), (5, 4, 2).

**Source:**LNU Penguins Contest 8### Submit a solution

Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|

Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|