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 ;
}