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

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

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