Jede der $N$ Kühe von Farmer John ($(4 \le N \le 16)$) hat eine eindeutige Nummer $S_{i}$ ($(1 \le S_{i} \le 25,000)$). Stolz tragen sie gangsterartig eine goldene Platte mit groß eingravierter Nummer um den kräftigen Hals.

Die rebellischen Kühe stellen sich zum Melken „durcheinander“ auf: Die Nummern jedes benachbarten Paars unterscheiden sich um mehr als $K$ ($(1 \le K \le 3400)$). Bei $N = 6$ und $K = 1$ passt 1, 3, 5, 2, 6, 4, aber 1, 3, 6, 5, 2, 4 nicht, weil 5 und 6 nebeneinander nur um 1 differieren.

Wie viele solche Anordnungen von $N$ Kühen gibt es?

Bei den ersten 10 Einreichungen erhältst du Ergebnisse auf einem Teil der echten Testdaten.

Eingabe

• Zeile 1: zwei durch Leerzeichen getrennte ganze Zahlen $N$ und $K$.
• Zeilen $2,\ldots,N+1$: Zeile $i+1$ enthält eine ganze Zahl, Nummer $S_{i}$ von Kuh $i$.

Ausgabe

• Zeile 1: eine ganze Zahl, die Anordnungen von $N$ Kühen. Das Ergebnis passt in 64 Bit.

Beispiele

Eingabe 1

4 1
3
4
2
1

Ausgabe 1

2

Hinweis

Die zwei Anordnungen sind: 3 1 4 2 2 4 1 3.

Teilaufgaben

Punkte:200

Aufgabenautor: Don Piele, 2007