큐브

Octavia는 장난감 중에 크기가 같은 큐브 $N$개를 가지고 있다. 큐브의 무게는 서로 다를 수도 있고, 같은 무게의 큐브가 있을 수도 있다. Octavia는 큐브를 길게 한 줄로 늘어놓고 노는 것을 좋아한다. 여러 시간 놀고 나서, 만들 수 있는 큐브 배열이 몇 가지인지 궁금해졌다.

큐브 배열은 $N$개의 정수로 표현하며, 각 정수는 초기 배열에서 해당 큐브의 무게이다. Octavia는 인접한 두 큐브의 무게 합이 $K$ 이하일 때에만 두 큐브를 서로 바꿀 수 있다. 이 연산은 인접한 임의의 쌍에 대해 원하는 만큼 반복할 수 있다. 큐브 무게의 수열이 다르면 두 배열은 서로 다른 배열이다.

예를 들어 무게가 $[1, 2, 1, 3]$인 큐브 4개와 $K = 3$인 경우를 보자. 가능한 배열은 3개이다. 첫 번째는 초기 배열이다. 두 번째는 2번째와 3번째 큐브를 바꿔 $[1, 1, 2, 3]$을 얻는다. 1번째와 3번째 큐브는 인접하지 않으므로 바꿀 수 없다. 3번째와 4번째 큐브는 무게 합이 4로 $K = 3$보다 크므로 바꿀 수 없다. 마지막 배열 $[2, 1, 1, 3]$은 처음 두 큐브를 바꿔서 얻는다. 같은 초기 배열에서 $K = 1$이면 가능한 배열은 1개뿐이다. $K = 2$일 때도 1개이다. $K = 4$이면 6개, $K = 5$이면 12개이다.

Octavia가 얻을 수 있는 서로 다른 큐브 배열의 개수를 구하는 프로그램 cubes를 작성하라.

첫 줄에 큐브의 개수 $N$과, 서로 바꿀 수 있는 인접한 두 큐브 무게 합의 최댓값 $K$가 주어진다. 둘째 줄에는 초기 배열에서의 무게 $w_1, \dots, w_N$이 양의 정수 $N$개로 주어진다.

가능한 배열의 개수를 $1\,000\,000\,007$로 나눈 나머지를 한 줄에 출력한다.

$1 \le N \le 300\,000$

$1 \le w_i, K \le 1\,000\,000\,000$

두 번째 경우에는 무게가 1과 3인 큐브만 서로 바꿀 수 있으므로 답은 2이다. 가능한 배열은 $[4, 3, 1, 5, 2]$와 $[4, 1, 3, 5, 2]$이다.