链接: https://cses.fi/problemset/task/2209

板块: Mathematics

时限: 1.00 s ｜ 内存: 512 MB

题目描述

你的任务是计数由 $n$ 颗珠子组成、且每颗珠子有 $m$ 种可选颜色的不同项链的数量。

如果无法通过旋转其中一条项链使它们看起来相同，则认为两条项链是不同的。

输入

唯一的输入行包含两个数 $n$ 和 $m$：分别表示珠子数和颜色数。

输出

输出一个整数：不同项链的数量对 $10^9+7$ 取模的结果。

数据范围

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

样例输入

4 3

样例输出

24