P3197 [HNOI2008] Prison Break

There are $n$ rooms in the prison, with one prisoner in each room. There are $m$ religions, and each prisoner believes in exactly one of them. If prisoners in adjacent rooms have the same religion, a prison break may occur. Count how many states may lead to a prison break. Output the answer modulo $100{,}003$.

The input contains a single line with two integers, the number of religions $m$ and the number of rooms $n$.

Output a single integer on one line representing the answer.

#### Sample Input/Output 1 Explanation | State ID | Room 1 | Room 2 | Room 3 | | :--------: | :--------: | :-------: | :--------: | | 1 | Religion 1 | Religion 1 | Religion 1 | | 2 | Religion 1 | Religion 1 | Religion 2 | | 3 | Religion 1 | Religion 2 | Religion 2 | | 4 | Religion 2 | Religion 1 | Religion 1 | | 5 | Religion 2 | Religion 2 | Religion 2 | | 6 | Religion 2 | Religion 2 | Religion 1 | #### Constraints For $100\%$ of the testdata, it is guaranteed that $1 \le m \le 10^8$, $1 \le n \le 10^{12}$. Translated by ChatGPT 5