题目描述

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$ 取模。

数据范围与约定

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

## 题目描述

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$ 取模。

#### 数据范围与约定

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