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

【说明】

本题不再额外提供样例文件。

【题目描述】

n 个格子围成一圈，第 i （1 ≤ i < n）个格子与第 i+1 个格子相邻，第 n 个与第 1 个格子相邻。这 n 个格子中间又围成一个椭圆形区域，我们将其视为第 n+1 个格子，该格子与初始的 n 个格子均相邻。如下图所示：

现在让你往 n+1 个格子里填数，每个格子只能填 1 ~ m 中的一个整数，不能不填，并且任意两个相邻的格子不能填相同的数字。 问：你有多少种不同的填法？答案可能很大，你需要将其 mod 1,000,000,007 后输出。 两种填法不同，当前仅当至少存在一个格子在两种填法中所填的数字不同。

【输入格式】

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

【输出格式】

每组数据的答案占一行。

【样例输入】

1 3
2 3
3 4
123456789 233333333

【样例输出】

6
6
24
637444390

【数据范围】

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

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