题目描述

给定两个正整数 $n$ 和 $k$，你需要将 $n$ 恰好分成 $k$ 份正整数（这 $k$ 份之和等于 $n$），使得这 $k$ 份的乘积尽可能大。

请求出这个最大乘积对 $10^9 + 7$ 取模后的结果。

输入格式

一行，两个正整数 $n, k$，用空格分隔。

输出格式

一行一个整数，表示最大乘积对 $10^9 + 7$ 取模后的结果。

输入输出样例 #1

输入 #1

10 2

输出 #1

25

输入输出样例 #2

输入 #2

20 4

输出 #2

625

输入输出样例 #3

输入 #3

10 3

输出 #3

36

说明/提示

【样例说明】

• 样例 1：将 $10$ 分成 $5 + 5$，乘积为 $5 \times 5 = 25$，这是最大的。
• 样例 2：将 $20$ 分成 $5 + 5 + 5 + 5$，乘积为 $5^4 = 625$，这是最大的。
• 样例 3：将 $10$ 分成 $4 + 3 + 3$，乘积为 $4 \times 3 \times 3 = 36$，这是最大的。

【数据范围】

对于 $100\%$ 的数据，$1 \le k \le n \le 10^{12}$。

【提示】

将 $n$ 尽量平均地分成 $k$ 份时，乘积最大。