问题1493--越狱（HNOI 2008）

1493: 越狱（HNOI 2008）

时间限制: 1 Sec  内存限制: 512 MB
提交: 17  解决: 5
[提交] [状态] [讨论版] [命题人:]

题目描述

监狱有连续编号为 1 到 n 的 n 个房间，每个房间关押一个犯人。有 m 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。求有多少种状态可能发生越狱。

输入

输入两个整数 m 和 n。

输出

可能越狱的状态数，对 100003 取余。

样例输入 Copy 

2 3

样例输出 Copy 

6

提示

样例说明


所有可能的 6 种状态为：{0,0,0},{0,0,1},{0,1,1},{1,0,0},{1,1,0},{1,1,1}。


数据范围与提示：


对于全部数据，1≤m≤108,1≤n≤1012。

来源/分类

数学基础 快速幂 
[提交] [状态]