思路：

总共有m^n次方种方案，其中相邻两个都不相同的有m * (m - 1) ^ (n - 1)种，两者相减就是答案

代码：

#include
     
      using namespace std;#define LL long long #define pb push_back#define mem(a, b) memset(a, b, sizeof(a)) const int mod = 1e5 + 3;LL q_pow(LL n, LL k) {    LL ans = 1;    while (k) {        if (k & 1) ans = (ans * n) % mod;        n = (n * n) % mod;        k >>= 1;     }    return ans;}int main() {    LL m, n;    scanf("%lld%lld", &m, &n);    LL tot = q_pow(m % mod, n);    LL tmp = (m % mod)*q_pow((m - 1) % mod, n - 1);    tot = ((tot - tmp) % mod + mod) % mod;     printf("%lld\n", tot);    return 0;}