Prison Breakout Count

There is a prison with n rooms, each holding one prisoner. There are m religions and each prisoner follows one of these religions. A breakout may happen if two adjacent rooms have prisoners of the same religion. Calculate the number of configurations which may trigger a breakout. The answer should be computed modulo 100,003.

The total number of possible configurations is \(m^n\). The number of configurations with no breakout (i.e. no two adjacent rooms having the same religion) is \(m\cdot (m-1)^{n-1}\). Therefore, the number of configurations that may trigger a breakout is given by:

\[ \text{answer} = m^n - m\cdot (m-1)^{n-1} \pmod{100003}. \]

inputFormat

The input consists of a single line containing two integers n and m, where:

• n (1 ≤ n) is the number of rooms.
• m (m ≥ 1) is the number of religions.

outputFormat

Output a single integer representing the number of configurations in which a breakout may happen, computed modulo 100,003.

sample

3 3

15