Description

Original Source: HNOI 2008

A prison has a sequence of $n$ rooms numbered consecutively from $1$ to $n$, each housing one prisoner. There are $m$ different religions, and each prisoner may follow one of them. If two adjacent prisoners share the same religion, an escape attempt may occur. Calculate the number of possible states where an escape could happen.

Input Format

Input two integers, $m$ and $n$.

Output Format

The number of possible escape states, modulo $100003$.

Sample 1

All possible $6$ states are: $\{0,0,0\},\{0,0,1\},\{0,1,1\},\{1,0,0\},\{1,1,0\},\{1,1,1\}$.

2 3

6

Constraints and Hints

For all test cases, $1\le m\le 10^8$ and $1\le n\le 10^{12}$.