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).
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 |
|---|