莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

$n\ 个吴亦犯，m\ 种宗教，如何安排才能保证吴亦犯不会越狱$

$1\ 号位置有\ m\ 种选择，与\ 1\ 号位置相邻的\ 2\ 号位置有\ m-1\ 种选择，同样\ 3\ 号位置也有\ m-1\ 种选择…$

$以此类推，那么不会越狱的方案：m\cdot(m-1)^{n-1}$

$故可以越狱的方案：m^n-m\cdot(m-1)^{n-1}$

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod = 100003;

int qmi(int a,LL b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(LL)res*a%mod;
        a=(LL)a*a%mod;
        b>>=1;
    }
    return res;
}

int main()
{
    int m;
    LL n;
    cin>>m>>n;
    cout<<(qmi(m,n)-(LL)m*qmi(m-1,n-1)%mod+mod)%mod<<endl;
    return 0;
}