传送门=￣ω￣=

思路

排列组合……首先我们可以算出不能越狱有多少种情况：第一个房间有 m 种可能（宗教），第二个房间因为不可以发生越狱，所以不能和第一个房间一样，所以是有（m-1）种可能，第三个房间同理，也是（m-1）种可能，以此类推。所以不能越狱共有：m×(m-1)^(n-1) 种可能。而总共有 m^n 种可能，所以最终答案为 m^n-m×(m-1)^(n-1) 。

所以很明显，用快速幂就行了，记得取膜。最后做减法可能会减出负数，所以要把答案加上 100003 再取膜。

还有！要开 long long！

代码

#include <iostream>
using namespace std;
typedef long long ll;
ll pow(ll a,ll b,ll mod)
{
    ll ans=1;a%=mod;
    while(b)
    {
        if(b&1)ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll m,n;
    cin>>m>>n;
    cout<<(pow(m,n,100003)-((m%100003)*pow(m-1,n-1,100003))%100003+100003)%100003;
    return 0;
}