1204 - Mixed up numbers

Time Limit: 5s Memory Limit: 128MB

Submissions: 158 Solved: 37
Description
We have N (4 <= N <= 16) different positive integers S_i (1 <= S_i <=25,000), and each of them is not larger than 25,000. Now we put them in a line but we don't want to get a "Mixed up" sequence. An order is "Mixed up" if the sequence is such that every pair of consecutive numbers in line differs by more than K(1 <= K <= 3400). For example, if N = 6 and K = 1, then "1, 3, 5, 2, 6, 4" is a "Mixed up" line, but "1, 3, 6, 5, 2, 4" is not (since the consectutive numbers 5 and 6 differ by 1). Then, how many different ways can N numbers be "Mixed up"?
Input
Line 1: Two space-separated integers: N and K Line 2..N+1: Line i+1 contains a single integer that is the ith number: S_i
Output
Line 1: A single integer that is the number of ways that N numbers can be "Mined up". The answer is guaranteed to fit in a 64-bit integer.
Sample Input
4 1
3
4
2
1
Sample Output
2
Hint
Source
Ai.Freedom