#M. 【USTCPC2025】M. 生成树！

Type: Default

1000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

克露丝卡尔酱喜欢生成树！

克露丝卡尔酱认为对称结构十分完美！

克露丝卡尔酱可爱！

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

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

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

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

一行一个正整数，表示答案。

input:

4 1

output:

input:

6 2

output:

两个样例中的轮分别为：