题意描述

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

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

如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

输入格式

输入仅有一行，包括两个整数 $m , n$，分别表示宗教数量与犯人数量。

输出格式

输出仅有一行，包含一个整数，表示可能越狱的状态数。

由于这个数可能比较大，因此，请输出该数模 $100003$ 取余的结果。

Input & Output ‘s examples

Input ‘s eg

2 3

Output ‘s eg

样例解释

6种状态为$(000)$,$(001)$,$(011)$,$(100)$,$(110)$,$(111)$

数据范围和约定

对于$30\%$的数据，保证$1 \leq m , n \leq 1000$

对于$100\%$的数据，保证$1 \leq m \leq 10^8$，$1 \leq n \leq 10^{12}$

分析

真正的组合数学入门题……

尝试直接做，发现直接统计多少人越狱会很麻烦。

考虑容斥。很容易看出，越狱的方案数等于总共的方案数减去不会越狱的方案数。

由于每一个房间信仰的宗教有$m$种可能，一共有$n$个房间，因此，总方案数为$m^n$。

现在考虑怎么样才不会越狱，显然，只有当两个房间信仰的宗教不同时才不会越狱。

也就是说，对于第一个房间，我们有$m$种选择，而剩下的房间要保证与之前的房间不同，每一间都有$(m - 1)$种可能。

综上，最终答案为$m^n - m * (m - 1)^{n - 1}$，直接快速幂计算即可。

剩下的见代码即可~~(这题应该不用写注释了吧)~~

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long 
#define I inline
#define N 100001
#define HA 100003


using namespace std;

ll n , m;

ll Pow(ll a , ll n){
    if(n == 0) return 1;
    if(n == 1) return a;
    ll c = Pow(a , n >> 1) % HA;
    if(n % 2 == 0){
        return c * c % HA;
    }
    else{
        return ((c * c) % HA * a) % HA;
    }
}

int main(){
    cin >> m >> n;
    ll ans =  Pow(m , n) - m * Pow(m - 1 , n - 1) % HA;
    ans += HA;
    cout << ans % HA << "\n";
    return 0;
}