在 X 星球上有一个名为 Y 的国家，它以治安条件良好、百姓安居乐业而闻名。正因为如此，在 Y 国犯罪人数很少，以至于全国只需要设置一个监狱就足够关押所有罪人。Y 国的监狱很有特点：它由 $n$ 个房间组成，所有的房间都紧挨着排成一排，而且每个房间只关押一个犯人。同时，Y 国是一个多宗教的国家，其境内流行着 $m$ 种宗教，并且每个公民都只信奉其中的一种宗教。

然而，近年来，Y 国的监狱里不时发生了犯人越狱的事件，这令 Y 国安全部长小 K 十分恼火。经过长期的调查，小 K 发现，发生越狱事件必须具备两个条件：首先，一个人的力量是有限的，因此越狱必须由两个相邻房间的犯人共同策划来完成；其次，两个拥有不同宗教信仰的人是不可能相互交流的，自然也不会共同策划越狱。

了解到这些情况后，小 K 十分高兴。他想知道，到底有多少种情况会导致越狱事件的发生。可是，小 K 数数的功夫自然比不过犯人的本事，于是他找到了准备参加 NOI2008 的你，请你编写一个程序，计算在所有房间都关满犯人的条件下（即，总共关押了 $n$ 个犯人），有多少种监狱的状态可能导致犯人越狱。

说明：

1. 越狱事件发生的充要条件是：存在两个相邻的房间，里面关押着两个拥有相同宗教信仰的人；
2. 一种“监狱的状态”是指一个 $n$ 元组 $(a_1,a_2,\cdots,a_n)$，其中 $0 \le a_i \le m-1$，表示第 $i$ 个房间的犯人拥有第 $a_i$ 种宗教信仰。

输入格式

只包含两个整数，并用一个空格隔开，第一个整数表示宗教的种数 $m$，第二个整数表示监狱中的房间 $n$。其中，$1 \le m \le 10^8$，$1 \le n \le 10^{12}$。

输出格式

仅包含一个整数，表示有多少种监狱的状态可能导致犯人越狱。由于这个数可能非常大，你只需输出它模 $100003$ 的余数即可。

样例数据

input

2 3

output

6

输入输出样例说明

6 种状态分别为 $(0,0,0)$、$(0,0,1)$、$(0,1,1)$、$(1,0,0)$、$(1,1,0)$、$(1,1,1)$。