问题 E: 越狱 - ZUFEOJ

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

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

提交：266 通过：95

返回比赛提交提交记录

监狱有连续编号为

1

到

n

的

n

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

m

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

输入两个整数 $m$ 和 $n$ 。

对于全部数据， $1 \leq m \leq 1 0^{8}, 1 \leq n \leq 1 0^{12}$ 。

可能越狱的状态数，对

100003

取余。

2 3

数学基础快速幂