문제
IOI가 곧 일본의 츠쿠바 시에서 열린다(2018년 IOI가 일본에서 열렸다.).IOI를 준비하기 위해, 츠쿠바 시의 중심 거리에 고층 건물을 건축하는 계획을 세우고 있다. 전망이 좋은 장소를 새로 만들고 싶기 때문에, 건축할 때 아래와 같은 조건을 만족해야 한다.
높이가 각각 A_1 , A_2 , A_3 , ... ,A_N인 N개의 건물을 짓고자 한다. N개의 건물의 순서를 아직 결정하지 않았기 때문에 필요하다면 건물의 순서를 마음대로 바꿀 수 있다. 이제 IOI를 맞이하여 그들을 꾸밀 것이다. 꾸미는 데 필요한 재료가 한정적이기 떄문에, 인접한 두 건물의 높이 차의 합이 L이하여야 한다. 다시 말해서, 재배열한 건물의 높이가 f_1 , f_2 , f_3 , ... , f_N 순서일 때 | f_1 - f_2 | + | f_2 - f_3 | + ... + | f_{N-1} - f_N | <= L을 만족해야 한다. 여기서 |x|는 x의 절댓값을 의미한다.
건물의 배열 중 위의 조건을 만족하는 개수는 몇 개인가?
건물의 수 N, 건물의 높이, 인접한 건물 사이 높이 차 합의 최대값인 L이 주어졌을 때, 조건을 만족하는 건물의 배열의 수를 출력하는 프로그램을 작성하여라. 답이 너무 커질 수 있으므로 1 000 000 007으로 나눈 나머지를 구하여라.
입력
첫 줄에는 건물의 개수 N과 인접한 건물 사이 높이 차 합의 최대값인 L이 N, L순으로 공백으로 구분되어 입력된다.
두 번째 줄에는 건물의 높이에 해당하는 A_1 , A_2 , ... , A_N이 순서대로 공백으로 구분되어 입력된다.
1 <= N <= 100
1 <= L <= 1000
1 <= A_i <= 1000 (1 <= i <= N)
A_i != A_j (1 <= i < j <= N)
출력
건물의 가능한 배열의 수를 1 000 000 007로 나눈 값을 출력하여라.
예제
4 10
3 6 2 9
6
로그인해야 코드를 작성할 수 있어요.