Description

克露丝卡尔酱想要计数 $n+1$ 个点的 $k$ 阶轮的生成树个数。

$n+1$ 个点的 $k$ 阶轮的定义为：

• $0$ 为中心，$1\sim n$ 构成一个环（对于 $1 \le i <n$，$i$ 和 $i+1$ 之间有连边，$1$ 和 $n$ 之间有连边）。
• 对于 $1 \le i \le \dfrac{n}{k}$，$0$ 和 $ik$ 之间有额外连边。

保证 $n \bmod k = 0$，答案对 $10^9+7$ 取模。

Input Format

一行两个正整数 $n,k$。$1 \le k \le n \le 10^{18}$，$n \ge 3$，保证 $n \bmod k = 0$。

Output Format

一行一个正整数，表示答案。答案对 $10^9+7$ 取模。

4 1

45

6 2

50

Hint

两个样例中的轮分别为：