antipalindrome (10.2hu測)

分析：

這個回文的限制，實際上就是：

a[i]!=a[i+1] && a[i]!=a[i+2]

很簡單的限制

我們直接用乘法原理就好了

ans=m*(m-1)*(m-2)^(n-2)

tip

在讀入之後m就%一下mod，

不然最後一個點會炸掉

n千萬别%

（指數應該%phi（mod），因為mod是一個質數，是以phi(mod)=mod-1，沒什麼必要）

費馬定理

A^x = A^(x % φ(p) + φ(p)) (mod p) x>=p

簡單來說就是如果模數是一質數，在計算快速幂的時候，可以直接把指數%(p-1)

//這裡寫代碼片
#include<cstdio>
#include<cstring>
#include<cstring>
#define ll long long

using namespace std;

const ll mod=;
ll n,m;

ll KSM(ll a,ll b)
{
    ll t=;
    a%=mod;
    while (b)
    {
        if (b&)
           t=(t%mod*a%mod)%mod;
        b>>=;
        a=(a%mod*a%mod)%mod;
    }
    return t%mod;
}

int main()
{
    freopen("anti.in","r",stdin);
    freopen("anti.out","w",stdout);
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%lld%lld",&n,&m);
        m%=mod;
        if (n==)
        {
            printf("%lld\n",m%mod);
        }
        else if (n==)
        {
            printf("%lld\n",(m%mod*(m-)%mod)%mod);
        }
        else
        {
            ll a=KSM(m-,n-);
            a=(a%mod*m%mod)%mod;
            a=(a%mod*(m-)%mod)%mod;
            printf("%lld\n",a);
        }
    }
    return ;
}