Problem Description

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$.

Input Format

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

Output Format

Output a single integer on one line representing the answer.

2 3

6

Hint

Sample Input/Output 1 Explanation

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