Marichka 的地下室里有很多土豆。有 $n$ 袋土豆排成一行，第 $i$ 袋包含 $a_i$ 个土豆。
Zenyk 喜欢洗这些袋子。在一次洗袋操作中，他可以选择两个相邻的袋子，如果这两个袋子中的土豆总数不超过 $k$，他就可以交换它们的位置。Zenyk 可以根据需要进行任意次数的洗袋操作。
Zenyk 和 Marichka 想知道，Zenyk 总共能实现多少种不同的袋子排列。如果两个排列在某个位置上的袋子所含土豆数量不同，则认为这两个排列是不同的。
输入格式
第一行包含两个整数 $n$ ($1 \le n \le 10^5$) 和 $k$ ($0 \le k \le 2 \cdot 10^9$)。第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le 10^9$)。
输出格式
输出一个整数，表示不同排列的数量，对 $10^9 + 7$ 取模。
样例
输入 1
3 7 5 2 4
输出 1
3
输入 2
5 4 1 2 3 2 1
输出 2
10