Cada uma das $N$ vacas de Farmer John ($(4 \le N \le 16)$) tem número único $S_{i}$ ($(1 \le S_{i} \le 25,000)$). Orgulhosas, usam uma placa dourada no pescoço largo com o número gravado em letras grandes, como gângsteres.

Rebeldes, alinham-se para ordenha na ordem «misturada»: os números de todo par consecutivo diferem por mais de $K$ ($(1 \le K \le 3400)$). Com $N = 6$ e $K = 1$, 1, 3, 5, 2, 6, 4 serve, mas 1, 3, 6, 5, 2, 4 não, pois 5 e 6 vizinhos diferem por 1.

Quantas formas há de misturar $N$ vacas?

Nas primeiras 10 submissões receberá resultados numa parte dos testes reais.

Entrada

• Linha 1: dois inteiros separados por espaço, $N$ e $K$.
• Linhas $2,\ldots,N+1$: a linha $i+1$ contém um inteiro, o número $S_{i}$ da vaca $i$.

Saída

• Linha 1: um inteiro, as formas para $N$ vacas. A resposta cabe em 64 bits.

Exemplos

Entrada 1

4 1
3
4
2
1

Saída 1

2

Nota

Os dois arranjos são: 3 1 4 2 2 4 1 3.

Subtarefas

Pontos:200

Autor do problema: Don Piele, 2007