Chacune des $N$ vaches de Farmer John ($(4 \le N \le 16)$) a un numéro unique $S_{i}$ ($(1 \le S_{i} \le 25,000)$). Fière, elle porte façon gangster une plaque d’or gravée en gros caractères autour de son large cou.

Rebelles, elles se rangent pour la traite dans un ordre «mélangé» : les numéros de toute paire consécutive diffèrent de plus de $K$ ($(1 \le K \le 3400)$). Avec $N = 6$ et $K = 1$, 1, 3, 5, 2, 6, 4 convient, mais 1, 3, 6, 5, 2, 4 non, car 5 et 6 consécutifs diffèrent de 1.

Combien de façons de mélanger $N$ vaches ?

Pour les 10 premières soumissions, les résultats sur une partie des vrais tests seront fournis.

Entrée

• Ligne 1 : deux entiers séparés par un espace, $N$ et $K$.
• Lignes $2,\ldots,N+1$ : la ligne $i+1$ contient un entier, le numéro $S_{i}$ de la vache $i$.

Sortie

• Ligne 1 : un entier, le nombre de façons pour $N$ vaches. Il tient dans un entier de 64 bits.

Exemples

Entrée 1

4 1
3
4
2
1

Sortie 1

2

Remarque

Les deux arrangements sont : 3 1 4 2 2 4 1 3.

Sous-tâches

Points :200

Auteur du problème : Don Piele, 2007