Magneti

시간 제한1초메모리 제한512 MB

요약

n개의 자석을 l칸 보드에 배치하는 방법의 수를 셉니다. 인접한 두 자석의 거리는 두 반지름 중 큰 값 이상이어야 하며, 답은 10^9+7로 나눈 나머지입니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 조합론, 정렬
정답자: 아직 제출이 없습니다

문제

어린 마르코는 시바 이누나 XRC 같은 수상한 암호화폐 놀이에 싫증이 나서 자석으로 놀기로 했다. 그에게는 서로 다른 자석 $n$ 개와, 자석을 놓을 수 있는 빈 칸이 한 줄로 $l$ 개 있는 보드가 있다. 인접한 두 칸의 간격은 정확히 1cm이다. 각 자석 $i$ 에는 활동 반경 $r_i$ 가 있다. 이 자석은 다른 자석의 반경과 상관없이, $r_i$ cm 미만으로 떨어진 모든 자석을 끌어당긴다. 반경이 같은 자석이 여러 개 있을 수 있지만, 이들은 서로 다른 자석으로 취급한다.

마르코는 자석끼리 서로 끌어당기는 것을 원하지 않는다. 어떤 자석도 다른 자석을 끌어당기지 않도록 자석을 배치하는 방법의 수를 구하라. 모든 자석은 보드 위에 놓여야 하며, 각 빈 칸에는 자석이 최대 하나만 들어갈 수 있다. 어떤 자석의 위치가 한쪽 배치와 다른 쪽 배치에서 다르면 두 배치는 서로 다른 것이다. 답은 $10^9 + 7$ 로 나눈 나머지로 출력한다.

입력

첫째 줄에 양의 정수 $n$ 과 $l$ 이 주어진다. 각각 자석의 개수와 빈 칸의 개수이다.

둘째 줄에는 양의 정수 $r_i$ 가 $n$ 개 주어진다. 각 값은 해당 자석의 활동 반경이다 ( $1 \le r_i \le l$ ).

출력

조건을 만족하는 배치 방법의 수를 $10^9 + 7$ 로 나눈 나머지를 출력한다.

제한

모든 서브태스크에서 $1 \le n \le 50$ , $n \le l \le 10\,000$ 이다.

힌트

두 번째 예제 설명: 어떤 두 자석도 서로 끌어당길 수 없으므로 자석의 모든 순열이 유효하다.

세 번째 예제 설명: 자석을 1, 2, 3으로, 빈 칸을 _로 나타내면 가능한 배치는 13_2, 31_2, 2_13, 2_31이다.

예제3

예제 1
입력
```
1 10
10
```
예상 출력
```
10
```
예제 2
입력
```
4 4
1 1 1 1
```
예상 출력
```
24
```
예제 3
입력
```
3 4
1 2 1
```
예상 출력
```
4
```