k = 1, 有n种方案，k = n时，有m^n种填数方案
可以把每次填数视为上图中的一条从1到n的路径（注意：一条边可能会走多次， 但是从n-1到n的边只会走一遍）
可以算出从1到2的兴奋度总和为3 * m * (m - 1) / 2, 但是总共要走m ^ (n - 2)遍
同样的，可以算出从2到3的兴奋度为3 * m * (m - 1) / 2   *   m, 但是只要走m ^ (n - 3) 遍
那么是否可以发现：从1到2总兴奋度 = 从2到3总兴奋度 = ... = 从n - 1到n的总兴奋度
是对的，因为相邻两层之间（k层， k + 1层）， k + 1层的路径是k层的m倍，但是要走的遍数是k层的1/m
故最终答案就是[3 * m * (m - 1) * m / 2 ^ ( n - 2)] * (n - 1)
下面是代码 
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
LL p(LL n, LL m)
{
    LL res = 1;
    while(m)
    {
        if(m & 1) res = (res * n) % mod;
        n = n * n % mod;
        m >>= 1;
    }
    return res;
}
int main ()
{
    int T;
    scanf("%d", &T);
    while(T --)
    {
        LL n, m;
        scanf("%lld%lld", &n, &m);
        LL ans = m * (m - 1) / 2 % mod;
        ans = ans * 3 % mod * (n - 1) % mod;
        ans = ans * p(m, n - 2) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}