【说明】

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

【题目描述】

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

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

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