宋荣子的城堡

题目描述

saruka 有一座大大的城堡!城堡里面有 $n$ 个房间,每个房间上面都写着一个数字 $p_i$。有一天,saruka 邀请他的小伙伴 LYL 和 MagHSK 来城堡里玩耍,他们约定,如果某一个人当前站在 $i$ 号房间里,那么下一步他就要去 $p_i$ 号房间,在下一步就要去 $p_{p_i}$ 号房间。 为了增加趣味性,saruka 决定重新书写一下每个房间的 $p_i$,以满足: - 如果从编号为 $1 \sim k$ 的某个房间走,按照规则走,必须能走回 $1$ 号房间。特别的,如果从 $1$ 号房间开始走,也要走回 $1$ 号房间。(至少走一步,如果 $p_1 = 1$,从 $1$ 走到 $1$ 也算合法)。 - 如果从编号大于 $k$ 的房间开始,按照规则走,一定不能走到 $1$ 号房间。 saruka 想知道,一共有多少书写 $p_i$ 的方案可以满足要求,答案对 $10 ^ 9 + 7$ 取模。

输入输出格式

输入格式


共一行两个数字 $n,k$,含义如题。

输出格式


一个数字,表示合法的方案数。答案对 $10 ^ 9 + 7$ 取模。

输入输出样例

输入样例 #1

5 2

输出样例 #1

54

输入样例 #2

7 4

输出样例 #2

1728

说明

对于 $100 \%$ 的数据,$1 \le n \le 10 ^ {18},1 \le k \le \min(n,8)$。