问题 4138 --3.[HNOI2008]越狱(Bzoj1008)

4138: 3.[HNOI2008]越狱(Bzoj1008)

题目描述

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

输入

输入两个整数 m 和 n。

输出

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

样例输入输出

输入#1 复制
2 3
输出#1 复制
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

序号 标题 作者 发表时间 费用 订购数 操作