saruka 有一座大大的城堡！城堡里面有 n 个房间，每个房间上面都写着一个数字 pi​。有一天，saruka 邀请他的小伙伴 LYL 和 MagHSK 来城堡里玩耍，他们约定，如果某一个人当前站在 i 号房间里，那么下一步他就要去 pi​ 号房间，在下一步就要去 ppi​​ 号房间。

为了增加趣味性，saruka 决定重新书写一下每个房间的 pi​，以满足：

• 如果从编号为 1∼k 的某个房间走，按照规则走，必须能走回 1 号房间。特别的，如果从 1 号房间开始走，也要走回 1 号房间。（至少走一步，如果 p1​=1，从 1 走到 1 也算合法）。

• 如果从编号大于 k 的房间开始，按照规则走，一定不能走到 1 号房间。

saruka 想知道，一共有多少书写 pi​ 的方案可以满足要求，答案对 109+7 取模。

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

一个数字，表示合法的方案数。答案对 109+7 取模。

对于 100% 的数据，1≤n≤1018,1≤k≤min(n,8)。