题目描述

一个长方形分成了 $n$ 个排成一行的方格，用 $m$ 种颜色去染色，要求相邻的两个方格颜色不同，求染色的方案数。

答案对 $100003$ 取模。

输入格式

一行，包含两个整数 $n$ 和 $m$ 。

输出格式

一行，包含一个整数表示染色的方案数。

样例

输入样例1

2 9

输出样例1

72

输入样例2

23476128 73946237

输出样例2

84495

数据范围与提示

$1\leq n \leq 10^{12} , \ \ 1\leq m \leq 10^8$ 。