Mixed Up Cows

Interview

Time limit1sMemory limit128 MB

Summary

Count permutations of N serial numbers (N at most 16) where every adjacent pair differs by more than K.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Combinatorics, Brute force
Solved: No attempts yet

Problem

Each of Farmer John's $N$ cows ( $4 \le N \le 16$ ) has a unique serial number $S_i$ ( $1 \le S_i \le 25000$ ).

The cows line up to be milked in an order called 'Mixed Up'. A lineup is 'Mixed Up' if, in the sequence of serial numbers formed by the line, every pair of consecutive cows has serial numbers that differ by more than $K$ ( $1 \le K \le 3400$ ). For example, if $N = 6$ and $K = 1$ , then the order $1, 3, 5, 2, 6, 4$ is 'Mixed Up', but $1, 3, 6, 5, 2, 4$ is not, because the consecutive numbers $5$ and $6$ differ by only $1$ .

How many different ways can the $N$ cows be lined up 'Mixed Up'?

Input

Line 1: Two space-separated integers $N$ and $K$ .
Lines 2 to $N+1$ : Line $i+1$ contains a single integer $S_i$ , the serial number of cow $i$ .

Output

Line 1: A single integer, the number of ways the $N$ cows can be lined up 'Mixed Up'. The answer is guaranteed to fit in a 64-bit integer.

Hint

For the sample, the $2$ possible 'Mixed Up' lineups are shown below, where each line lists the cows' serial numbers in order.

3 1 4 2
2 4 1 3

Examples2

Example 1
Input
```
4 1
3
4
2
1
```
Expected output
```
2
```
Example 2
Input
```
6 1
1
2
3
4
5
6
```
Expected output
```
90
```