Farmer John의 소 $N$마리($(4 \le N \le 16)$)는 각자 고유 번호 $S_{i}$($(1 \le S_{i} \le 25,000)$)가 있습니다. 매우 자랑스러워 번호를 큰 글씨로 새긴 금판을 굵은 목에 걸고 갱스터처럼 다닙니다.

반항적인 소들은 ‘뒤섞인’ 순서로 우유를 짜려 줄섭니다. 모든 인접한 두 소의 번호 차이가 $K$($(1 \le K \le 3400)$)보다 커야 합니다. $N = 6$, $K = 1$이면 1, 3, 5, 2, 6, 4는 맞지만 1, 3, 6, 5, 2, 4는 이웃5와6의 차가1이므로 아닙니다.

$N$마리를 뒤섞는 방법은 몇 개인가요?

첫10번 제출에는 실제 테스트 자료 일부에서 실행 결과가 주어집니다.

입력

• 1행: 공백으로 구분한 두 정수 $N$와 $K$.
• $2,\ldots,N+1$행: $i+1$행은 소 $i$의 번호 $S_{i}$인 정수 하나입니다.

출력

• 1행: $N$마리의 방법 수인 정수. 답은64비트 정수에 들어갑니다.

예제

입력 1

4 1
3
4
2
1

출력 1

2

참고

두 배열은 다음과 같습니다: 3 1 4 2 2 4 1 3.

서브태스크

점수:200

문제 작성자: Don Piele, 2007