Un jour, JOI-kun a obtenu une machine à voyager dans le temps. Il a décidé de se rendre au Japon au IXe siècle. Il y a rencontré Kukai, l'un des prêtres les plus célèbres du Japon à cette époque. Le prêtre souhaitait mettre au point une nouvelle méthode d'entraînement.

Son entraînement se déroule de la façon suivante :

• Kukai lit un sutra comportant $N$ phrases. Ces phrases sont ordonnées et il doit les lire dans cet ordre.
• Chaque phrase porte un entier compris entre $1$ et $N$, bornes incluses. Deux phrases différentes ne portent jamais le même nombre.
• Il doit lire la phrase portant l'entier $i$ ($1 \le i \le N$) pendant la $i$-ème période parmi les $N$ périodes de même durée qui divisent une journée. Chaque phrase est suffisamment courte pour qu'il soit toujours possible de la lire en une période.

Kukai souhaite lire tout le sutra aussi vite que possible. Cependant, le nombre de jours nécessaires dépend des entiers portés par les phrases du sutra. Kukai a demandé à JOI-kun de compter le nombre de façons d'attribuer les entiers aux phrases pour lesquelles il lui faut exactement $K$ jours pour terminer la lecture, s'il lit de manière optimale.

Tâche

Étant donnés le nombre de phrases $N$ et un entier $K$, calculez, modulo $1\,000\,000\,007$, le nombre de façons d'attribuer les entiers aux phrases pour lesquelles Kukai met exactement $K$ jours à terminer la lecture, s'il lit de manière optimale.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne de l'entrée contient $N$ et $K$, séparés par une seule espace.

Sortie

Affichez, modulo $1\,000\,000\,007$, le nombre de façons d'attribuer les entiers aux phrases pour lesquelles Kukai met exactement $K$ jours à terminer la lecture, s'il lit de manière optimale.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

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

Sous-tâches

Il y a 4 sous-tâches. Le score et les contraintes supplémentaires de chacune sont les suivants :

Sous-tâche 1 [4 points]

• $N \le 10$.

Sous-tâche 2 [20 points]

• $N \le 300$.

Sous-tâche 3 [25 points]

• $N \le 3\,000$.

Sous-tâche 4 [51 points]

Il n'y a aucune contrainte supplémentaire.

Exemples

Entrée 1

3 2

Sortie 1

4

Remarque

Il existe 4 façons d'attribuer les entiers aux phrases pour lesquelles il met 2 jours à terminer la lecture.

• La première phrase porte $1$, la suivante porte $3$ et la dernière porte $2$. Il lit les deux premières phrases (portant respectivement les nombres $1$ et $3$) le premier jour, puis la dernière phrase (portant le nombre $2$) le deuxième jour.
• La première phrase porte $2$, la suivante porte $1$ et la dernière porte $3$.
• La première phrase porte $2$, la suivante porte $3$ et la dernière porte $1$.
• La première phrase porte $3$, la suivante porte $1$ et la dernière porte $2$.

Entrée 2

10 5

Sortie 2

1310354