题面
题目描述
监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
输入输出格式
输入格式：
输入两个整数M，N.1<=M<=10^8,1<=N<=10^12
输出格式：
可能越狱的状态数，模100003取余
输入样例#1：
2 3
输出样例#1：
6
题解
这种题目不会做？？？
这么显然的排列组合
正难则反
减去合法的方案就行啦。。。
超简单的题目呀。。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;
#define ll long long
inline ll read()
{ll x=0,t=1;char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return x*t;
}
#define MOD 100003
ll Pow(ll a,ll b)
{ll s=1;while(b){if(b&1)s=s*a%MOD;a=a*a%MOD;b>>=1;}return s;
}
int main()
{ll M=read(),N=read();printf("%lld\n",(Pow(M,N)-Pow(M-1,N-1)*M%MOD+MOD)%MOD);return 0;
}