시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 256 MB 3 2 (67%) 2
문제
고대 바빌로니아인들은 거대한 탑을 짓기로 했다. 그리고 그 탑은 $N$개의 정육면체 블럭을 쌓아서 만들기로 하였다. 바빌로니아인들은 전국을 돌며 다양한 크기의 블럭들을 모았다. 그들은 앞선 실패를 통해 큰 블럭을 비교적 많이 작은 블럭 바로 위에 놓으면 탑이 무너진다는 사실을 알게 되었다. 각 블럭들에 대해 변의 길이가 주어지고 그들의 크기가 같더라도 서로 다르게 취급한다. 이때 정수 $D$가 주어지는데 이는 블럭 $A$의 변의 길이가 블럭 $B$의 변의 길이에 $D$를 더한 값보다 크다면 블럭 $A$를 블럭 $B$ 위에 놓을 수 없다는 것을 의미한다. 모든 블럭들을 사용하여 탑을 쌓을 수 있는 경우의 수를 계산하라. 이 수는 매우 커질 수 있으므로 $10^9+9$로 나눈 나머지를 출력하라.
입력
첫째 줄에 띄어쓰기로 구분된 두 개의 정수 $N, D$가 주어진다. $N$은 블럭의 개수이고 $D$는 앞서 설명한 값이다.
둘째 줄에는 $N$개의 블럭의 크기들이 띄어쓰기로 구분되어 주어진다.
출력
가능한 탑쌓기의 가지수를 $10^9+9$로 나눈 나머지를 출력한다.
힌트
#### 제약조건 입력의 모든 숫자는 $10^9$을 넘지 않는 양의 정수이다.
$N$은 항상 $2$이상이다.
$70$점에 해당하는 서브태스크에서 $N$은 최대 $70$이다.
나머지 중 $45$점에 해당하는 서브태스크에서 $N$은 최대 $20$이다.
나머지 중 $10$점에 해당하는 서브태스크에서 $N$은 최대 $10$이다.
일부 서브태스크에서 탑을 쌓는 경우의 수는 $1,000,000$가지 이하이다. 이런 경우들을 다 합하면 $30$점에 해당한다.
마지막 $6$개의 서브태스크($30$점에 해당)에서 $N$은 $70$이상이다. 이 경우 $N$의 상한은 주어지지 않는다. 시간 제한은 $1$초, 메모리 제한은 $256MB$이다. #### 입력 예시 1 ``` 4 1 1 2 3 100 ``` #### 출력 예시 1 ``` 4 ``` 처음 3개의 블럭은 2,1,3 과 1,3,2 같은 순서를 제외하고 아무렇게나 배치할 수 있고 마지막 블럭은 항상 맨 바닥에 있어야 한다. #### 입력 예시 2 ``` 6 9 10 20 20 10 10 20 ``` #### 출력 예시 2 ``` 36 ``` 크기 20의 블럭을 크기 10짜리 블럭 위에 놓을 수 없고 각각 크기가 같은 블럭끼리 배치 가능한 순서가 6가지씩 존재한다.