Description

监狱有连续编号为 \(1, 2, ..., n\) 的 \(n\) 个房间, 每个房间关押一个犯人, 有 \(m\) 种宗教, 每个犯人可能信仰其中一种. 如果相邻房间的犯人的宗教相同, 就可能发生越狱, 求有多少种状态可能发生越狱

Input

输入两个整数 \(m, n\).\(1 \leq m \leq 10^8, 1 \leq n \leq 10^{12}\)

Output

可能越狱的状态数, 模 \(100003\) 取余

Sample Input

2 3

Sample Output

6

Explanation

如果我们从另一个方面想问题, 就是说所有的排列方法, 减去相邻两个不同的方法数:

所有的排列方法数为 \(m^n\) 种, 而相邻不同的方法数为: 考虑第一个位置有 \(m\) 种涂法, 从第二个位置开始起, 每一个位置只是不能涂前一种颜色, 所以有 \(m-1\) 种涂法, 固然, 总的会发生事故的方案数为:

\[m^n - (m-1)^{n-1}\]

然后简单快速幂瞎搞一发就可以了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 10010;
const lli modr = 100003;

lli power(lli a, lli b) {
    lli x = a, res = 1;
    for (lli i = 0; i < 64; i++) {
        if (b & (1ll << i)) res = res * x % modr;
        x = x * x % modr;
    } return res; }

lli n, m;

int main(int argc, char** argv)
{
    scanf("%lld%lld", &m, &n);
    lli res = (power(m, n) + modr - m * power(m - 1, n - 1) % modr) % modr;
    printf("%lld\n", res);
    return 0;
}