题目描述
*有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
输入输出格式
输入格式：
输入两个整数M，N.1<=M<=10^8,1<=N<=10^12
输出格式：
可能越狱的状态数，模100003取余
输入输出样例
输入样例#1：
2 3
输出样例#1：
6
说明
6种状态为(000)(001)(011)(100)(110)(111)
简单到不像省选题，原本打算用半小时，结果只用了5分钟
所有状态m^n,不符合条件的状态：
第一个有m种选择,接下来n-1个为(m-1)种，所以总数：m*(m-1)^(n-1)
ans=m^n-m*(m-1)^(n-1)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int p=;
long long ans1,ans2;
long long qpow(long long x,long long m)
{
if (m==) return ;
long long tmp=qpow(x,m/);
tmp=(tmp*tmp)%p;
if (m%==) tmp=(tmp*x)%p;
return tmp;
}
int main()
{long long m,n;
cin>>m>>n;
ans1=qpow(m,n);
ans2=(m*qpow(m-,n-))%p;
cout<<(ans1-ans2+p)%p;
}