Ognuna delle $N$ mucche di Farmer John ($(4 \le N \le 16)$) ha numero unico $S_{i}$ ($(1 \le S_{i} \le 25,000)$). Ne sono fiere e portano come gangster una placca d’oro con il numero inciso in grandi lettere intorno al grosso collo.

Ribelli, si mettono in fila per la mungitura «mescolate»: i numeri di ogni coppia consecutiva differiscono per più di $K$ ($(1 \le K \le 3400)$). Con $N = 6$ e $K = 1$, 1, 3, 5, 2, 6, 4 va bene, 1, 3, 6, 5, 2, 4 no, perché 5 e 6 adiacenti differiscono di 1.

In quanti modi mescolare $N$ mucche?

Per le prime 10 consegne avrai i risultati su parte dei test reali.

Input

• Riga 1: due interi separati da spazio, $N$ e $K$.
• Righe $2,\ldots,N+1$: riga $i+1$ contiene un intero, numero $S_{i}$ della mucca $i$.

Output

• Riga 1: un intero, i modi per $N$ mucche. Il risultato entra in 64 bit.

Esempi

Input 1

4 1
3
4
2
1

Output 1

2

Nota

I due ordini sono: 3 1 4 2 2 4 1 3.

Sottoproblemi

Punti:200

Autore del problema: Don Piele, 2007