C# one-line

public static int solve(int n, int m)
{
    return n == 1 ? m%1000000007: (int)((BigInteger.ModPow(m-2, n-2,1000000007)*m*(m-1)) % 1000000007);
}

..without BigInteger would be longer :)

Here's my solution in JAVA:

    static int solve(int n, int m) {

        if (n == 1) return m%(1000000007);
    
BigInteger result = new BigInteger(""+m);
result = result.multiply(new BigInteger(""+(m-1)));
BigInteger newBig = new BigInteger(""+(m-2));
newBig = newBig.modPow(new BigInteger(""+(n-2)),new BigInteger("1000000007"));
result = result.multiply(newBig);


        return result.mod(new BigInteger("1000000007")).intValue();

    }

C++

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const ll inf = 1e18 + 1;
const ll mod = 1e9 + 7;

ll power(ll x, ll y, ll M = inf){
    ll ans = 1;
    x %= M;
    while(y){
        if(y&1)
            ans = (x * ans) % M;

        x = (x * x) % M;
        y >>= 1;
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1;
    cin>>t;
    while(t--){
        ll n, m;
        cin>>n>>m;
        if(n==1) cout<<m<<"\n";
        else if(n==2) cout<<(m*(m-1))%mod<<"\n";
        else{
            ll ans = (m*(m-1))%mod;
            ans *= power(m-2, n-2, mod);
            cout<<ans%mod<<"\n";
        }
    }
    return 0;
}

Since this problem requires processing of integers exceeding 2^64, I would not recommend attemping to solve it using a language that does not provide support for "big integers", eg use Java or C# and not Javascript. Also, note that in order to meet execution time constraints you need to use a modular exponentiation algorithm such as that provided by Java's BigInt.modPow() to compute (N - 2)^(M - 2), otherwise some tests will time out. Finally note that the output must be displayed modulo 1000000007 (shown cryptically as "10^9 + 7" in the problem text). I mention these things because it seems clear from the discussions that many submitters missed these issues due to lack of clarity in the problem statement.

To the HR folks I suggest reviewing the challenge desciptions for clarity and completeness. Given that employers use your system to evaluate job candidates it is important that the descriptions be clearly presented and IMHO many of them are not. Here are some suggestions for improving clarity:

• clealy written with correct grammar
• use mnemonics for inputs, eg phraseLengh and maxCharacters instead of M and N
• list execution time constraints if problem is performance oriented
• complete examples, eg in this problem a segmentLength of four would have clarified the "any palidrome" concept
• express constants in standard form, eg 1000000007 and not 10^9 + 7.

In case if you are trying to do it in a DP fashion to calculate the amount of length(n-1) with set cardinality of m, don't do it ... It won't work. :/