고층 건물

국제정보올림피아드는 일본의 Tsukuba City에서 개최된다. IOI을 준비하기 위해, 우리는 Tsukuba City의 중심가에 고층 건물들을 건설할 계획이다. 새로운 관광 명소를 만들고자 하므로, 건물들은 다음 조건을 만족해야 한다. 우리는 중심가의 직선을 따라 N개의 건물을 건설할 계획이다. 건물들의 높이는 A1 , A2 , A3 , . . . , AN 이다. 이 높이들은 서로 다르다. N개 건물의 순서는 아직 정해지지 않았으므로, 필요하다면 높이들의 순서를 바꿀 수 있다. 우리는 IOI을 위해 건물들을 장식할 것이다. 장식에 사용되는 재료의 제약 때문에, 인접한 두 건물의 높이 차이의 절댓값의 합은 L 이하여야 한다. 다시 말해, 중심가의 한쪽에서부터 본 건물들의 높이가 f1 , f2 , f3 , . . . , fN 이라면, | f1 − f2 | + | f2 − f3 | + . . . + | fN−1 − fN | ≤ L 을 만족해야 한다. 여기서 |x|는 x의 절댓값이다. 위 조건을 만족하는 건물의 순열은 몇 개인가?

건물의 수 N, 건물들의 높이, 인접한 두 건물의 높이 차이의 절댓값의 합의 상한 L이 주어질 때, 조건을 만족하는 건물 순열의 수를 계산하는 프로그램을 작성하라. 이 수는 매우 클 수 있으므로, 이를 1 000 000 007로 나눈 나머지를 출력한다.

제약 조건

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ N ≤ 100.

• 1 ≤ L ≤ 1 000.

• 1 ≤ Ai ≤ 1 000 (1 ≤ i ≤ N).

• A_i, A_j (1 ≤ i < j ≤ N).

부분 과제

부분 과제 1 [5점] • N ≤ 8.

부분 과제 2 [15점] 다음 조건을 만족한다.

• N ≤ 14.

• L ≤ 100.

부분 과제 3 [80점] 추가 제약 조건은 없다.

표준 입력에서 다음 데이터를 읽는다.

• 입력의 첫째 줄에는 공백으로 구분된 두 정수 N, L이 주어진다. 이는 건물의 수가 N이고, 인접한 두 건물의 높이 차이의 절댓값의 합의 상한이 L임을 뜻한다.

• 둘째 줄에는 공백으로 구분된 N개의 정수 A1 , A2 , A3 , . . . , AN 이 주어진다. 이는 i번째 건물의 높이 (1 ≤ i ≤ N)가 Ai임을 뜻한다.

출력은 한 줄로 이루어진다. 조건을 만족하는 건물 순열의 수를 1 000 000 007로 나눈 나머지인 정수를 출력한다.