Problem1634--越狱

1634: 越狱

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 200  Solved: 43
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI当了狱警,他的工作是要排查所有发生越狱的可能。
监狱有连续编号为1到n的n个房间,每个房间关押一个犯人。
有m种宗教,每个犯人可能信仰其中一种,不存在没有信仰的犯人。
如果相邻房间的犯人信仰的宗教相同,就可能发生越狱。
PIPI想要计算出有多少种状态可能发生越狱。

Input

多组输入
每组输入共一行,包含两个整数m和n
1<=m<=1e8
1<=n<=1e12

Output

对于每组数据,输出可能的越狱状态数,并对100003取余。

Sample Input

2 3

Sample Output

6

Source/Category

简单