#CS2209. 项链计数

项链计数

题目背景

翻译自 CSES-2209 题。

题目描述

你的任务是计算由 n 个珍珠组成的不同项链的数量，每个珍珠有 m 种可能的颜色。

两个项链被认为是不同的，当且仅当无法通过旋转其中一个项链使其与另一个项链完全相同。

输入格式

唯一的输入行包含两个整数 n 和 m：分别表示珍珠的数量和颜色的种类数。

输出格式

输出不同项链的数量，结果对 109+710^9+7109+7 取模。

样例

4 3

24

说明/提示

$1 \leq n,m \leq 10^6$