问题 E: 越狱 - ZUFEOJ

内存限制：128 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：270 通过：96

返回比赛提交提交记录

监狱有连续编号为

1

到

n

的

n

个房间，每个房间关押一个犯人。有

m

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

输入两个整数

m

和

n

。
对于全部数据，

1 \leq m \leq 1 0^{8}, 1 \leq n \leq 1 0^{12}

。

可能越狱的状态数，对

100003

取余。

2 3

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

数学基础快速幂