题目描述

有一天，JOI 君得到了一台时光机。他决定前往 9 世纪的日本。在那里，他遇到了当时日本最著名的僧侣之一——空海。这位僧侣希望开发一种新的修行方式。

他的修行方式如下：

• 空海阅读一部包含 $N$ 句经文的经书。这些经文是有序的，他必须按顺序阅读。
• 每句经文上标有一个介于 $1$ 到 $N$（含）之间的整数，且任意两句不同的经文所标数字不同。
• 他必须在一天中被均分为 $N$ 个时间段的第 $i$ 个时间段内阅读标有整数 $i$（$1 \le i \le N$）的那句经文。每句经文都很短，因此他总能在每个时间段内读完一句经文。

空海希望尽快读完整部经书。然而，他完成阅读所需的天数取决于经文上所标整数的排列方式。JOI 君被空海要求计算：在最优阅读策略下，有多少种整数分配方式能使空海恰好用 $K$ 天完成阅读。

任务

给定经文数量 $N$ 和整数 $K$，计算在最优阅读策略下，能使空海恰好用 $K$ 天完成阅读的整数分配方式的总数，结果对 $1\,000\,000\,007$ 取模。

输入格式

从标准输入读取以下数据：

• 输入第一行包含两个整数 $N$ 和 $K$，以单个空格分隔。

输出格式

输出在最优阅读策略下，能使空海恰好用 $K$ 天完成阅读的整数分配方式的总数，结果对 $1\,000\,000\,007$ 取模。

3 2

4

10 5

1310354

提示

样例 1 解释

共有 4 种整数分配方式，能使他恰好用 2 天完成阅读：

• 第一句经文标有 $1$，第二句标有 $3$，最后一句标有 $2$。他在第一天阅读前两句经文（分别标有 $1$ 和 $3$），在第二天阅读最后一句经文（标有 $2$）。
• 第一句经文标有 $2$，第二句标有 $1$，最后一句标有 $3$。
• 第一句经文标有 $2$，第二句标有 $3$，最后一句标有 $1$。
• 第一句经文标有 $3$，第二句标有 $1$，最后一句标有 $2$。

数据范围

所有输入数据满足以下条件：

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

子任务

共有 4 个子任务。每个子任务的得分和附加约束如下：

子任务 1 [4 分]

• $N \le 10$。

子任务 2 [20 分]

• $N \le 300$。

子任务 3 [25 分]

• $N \le 3\,000$。

子任务 4 [51 分]

无额外约束。