On planet X, there is a country called Y, known for its excellent public security and the peaceful, contented lives of its citizens. Because of this, the number of criminals in country Y is so small that a single prison is sufficient to house all of them. The prison in country Y has a unique design: it consists of $n$ rooms arranged in a single row, with each room housing exactly one prisoner. Additionally, country Y is a multi-religious nation where $m$ different religions are practiced, and every citizen adheres to exactly one of these religions.

However, in recent years, prison breaks have occurred from time to time, which has greatly annoyed the Minister of Security, Xiao K. After a long investigation, Xiao K discovered that two conditions must be met for a prison break to occur: first, because an individual's power is limited, a prison break must be planned jointly by prisoners in two adjacent rooms; second, two people with different religious beliefs cannot communicate with each other and, naturally, will not plan a prison break together.

Upon learning this, Xiao K was very pleased. He wanted to know how many possible scenarios could lead to a prison break. However, Xiao K's counting skills are no match for the prisoners' ingenuity, so he has turned to you, a participant in NOI2008, to write a program that calculates how many prison states could lead to a prison break, given that all rooms are occupied (i.e., there are a total of $n$ prisoners).

Note:

1. The necessary and sufficient condition for a prison break to occur is: there exist two adjacent rooms containing prisoners who share the same religious belief.
2. A "prison state" is defined as an $n$-tuple $(a_1, a_2, \dots, a_n)$, where $0 \le a_i \le m-1$, representing that the prisoner in the $i$-th room adheres to the $a_i$-th religion.

Input

The input contains only two integers separated by a space. The first integer represents the number of religions $m$, and the second integer represents the number of rooms in the prison $n$. Here, $1 \le m \le 10^8$ and $1 \le n \le 10^{12}$.

Output

Output a single integer representing the number of prison states that could lead to a prison break. Since this number can be very large, you only need to output the remainder when divided by $100003$.

Examples

Input 1

2 3

Output 1

6

Note

The 6 states are $(0,0,0)$, $(0,0,1)$, $(0,1,1)$, $(1,0,0)$, $(1,1,0)$, and $(1,1,1)$.