Eines Tages bekam JOI-kun eine Zeitmaschine. Er beschloss, nach Japan ins 9. Jahrhundert zu reisen. Dort traf er Kukai, einen der damals berühmtesten Priester Japans. Der Priester wollte eine neue Methode der Übung entwickeln.

Seine Übung läuft wie folgt ab:

• Kukai liest eine Sutra mit $N$ Sätzen. Die Sätze haben eine feste Reihenfolge und müssen in dieser Reihenfolge gelesen werden.
• Jeder Satz trägt eine ganze Zahl zwischen $1$ und $N$ einschließlich. Keine zwei verschiedenen Sätze tragen dieselbe Zahl.
• Er muss den Satz mit der Zahl $i$ ($1 \le i \le N$) im $i$-ten der $N$ gleich langen Zeitabschnitte eines Tages lesen. Jeder Satz ist so kurz, dass er ihn immer innerhalb eines Zeitabschnitts lesen kann.

Kukai möchte die gesamte Sutra so schnell wie möglich lesen. Wie viele Tage er dafür benötigt, hängt jedoch von den Zahlen auf den Sätzen der Sutra ab. Kukai bat JOI-kun, die Anzahl der möglichen Zuordnungen von Zahlen zu den Sätzen zu zählen, bei denen Kukai bei optimalem Lesen genau $K$ Tage benötigt.

Aufgabe

Gegeben sind die Anzahl der Sätze $N$ und eine ganze Zahl $K$. Berechne die Anzahl der möglichen Zuordnungen von Zahlen zu den Sätzen, bei denen Kukai bei optimalem Lesen genau $K$ Tage benötigt, modulo $1\,000\,000\,007$.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Eingabezeile enthält $N$ und $K$, getrennt durch ein einzelnes Leerzeichen.

Ausgabe

Gib die Anzahl der möglichen Zuordnungen von Zahlen zu den Sätzen aus, bei denen Kukai bei optimalem Lesen genau $K$ Tage benötigt, modulo $1\,000\,000\,007$.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $1 \le N \le 100\,000$.
• $1 \le K \le N$.

Teilaufgaben

Es gibt 4 Teilaufgaben. Ihre Punktzahlen und zusätzlichen Beschränkungen sind wie folgt:

Teilaufgabe 1 [4 Punkte]

• $N \le 10$.

Teilaufgabe 2 [20 Punkte]

• $N \le 300$.

Teilaufgabe 3 [25 Punkte]

• $N \le 3\,000$.

Teilaufgabe 4 [51 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

3 2

Ausgabe 1

4

Hinweis

Es gibt $4$ mögliche Zuordnungen von Zahlen zu den Sätzen, bei denen er $2$ Tage zum vollständigen Lesen benötigt.

• Der erste Satz trägt die Zahl $1$, der nächste die Zahl $3$ und der letzte die Zahl $2$. Er liest die ersten beiden Sätze mit den Zahlen $1$ beziehungsweise $3$ am ersten Tag und den letzten Satz mit der Zahl $2$ am zweiten Tag.
• Der erste Satz trägt die Zahl $2$, der nächste die Zahl $1$ und der letzte die Zahl $3$.
• Der erste Satz trägt die Zahl $2$, der nächste die Zahl $3$ und der letzte die Zahl $1$.
• Der erste Satz trägt die Zahl $3$, der nächste die Zahl $1$ und der letzte die Zahl $2$.

Eingabe 2

10 5

Ausgabe 2

1310354