不越狱:考虑第一个人,它可以信仰1-m任意一种可能的宗教, 共m种,下一个人和它的信仰不能相同,所以有m-1种,....后面m-2个人依次类推。
故总不越狱的情况有$m\*(m-1)^{n-1}$种
而总的排列情况有$m^n$种,减去不越狱的情况即可,结果取模
#include<iostream>
using namespace std;
const int mod = 100003;
typedef long long LL;
LL m, n;
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() {
cin >> m >> n;
LL res = qmi(m, n) - (LL)m * qmi(m - 1, n - 1);
cout << ((res % mod) + mod) % mod << endl;
return 0;
}