越狱

监狱有连续编号为 1 到 n 的 n 个房间，每个房间关押一个犯人。

有 m 种宗教，每个犯人可能信仰其中一种。

如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。

求有多少种状态可能发生越狱。

输入格式

共一行，包含两个整数 m 和 n。

输出格式

可能越狱的状态数，对 100003 取余。

数据范围

1≤m≤108 1≤n≤1012

输入样例：
2 3
输出样例：
6

样例解释

所有可能的 6 种状态为：(000)(001)(011)(100)(110)(111)。

#include "iostream"

using namespace std;

typedef long long ll;

const int mod = 100003;

int quick_pow(ll base, ll pow) {
    ll res = 1;
    while (pow) {
        if (pow & 1) res = (res * base) % mod;
        pow >>= 1;
        base = (base * base) % mod;
    }
    return res;
}

int main() {
    ll n, m;
    scanf("%lld%lld", &m, &n);
    printf("%lld\n", (quick_pow(m, n) - m * quick_pow(m - 1, n - 1) % mod + mod) % mod);
    //例如模数是 10，那么 11 - 8 取模以后就是 1 - 8 是负数
    return 0;
}