该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

无额外样例。

题目描述

n 个格子围成一圈，第 i （1 ≤ i < n）个和第 i+1 个格子相邻，第 n 个和第 1 个格子相邻。

现在要往格子里填数，每个格子只能填一个不超过 m 的正整数，不能不填，并且任意两个相邻的格子不能填相同的数。

问：有多少种不同的填法？答案可能很大，你需要输出答案 mod $(10^9+7)$。

注：两种填法不同，当前仅当至少存在一个格子在两种填法中所填的数不同。

输入

多组数据，每组数据占一行，包含两个整数 n 和 m

输出

每组数据的答案占一行。

输入样例

1 3
2 3
3 4
1234567 7654321
123456789 233333333

输出样例

3
6
24
837608809
62940794

数据范围

40% 的数据：$0 < n, m ≤ 10^3$

70% 的数据：$0 < n, m ≤ 10^7$

100% 的数据：$0 < n, m ≤ 10^9$， 数据组数不超过 $20$。