作为一名懒人，Shik 在解决与字符串相关的题目时非常依赖哈希。以下是一个用 C 语言实现的简单哈希函数：

int hash(int n, int m, int p, const char *s) {
int h = 0;
for (int i = 0; i < n; i++) h = (h * p + s[i]) % m;
return h;
}

如果一对不同的字符串（无序对）具有相同的哈希值，我们称这对字符串为一个“冲突对”。Shik 声称自己非常幸运，哈希冲突的概率微乎其微。为了验证他的说法，你想在给定 $n, m, p$ 的情况下计算冲突对的数量。这里我们只考虑仅由大写字母 'A' 到 'Z' 组成的字符串。注意，因为给定了 $n$，字符串的长度必须恰好为 $n$。由于该数量可能非常大，你只需要输出它模 $10^6 + 3$ 的余数。

输入格式

输入恰好包含一行，有三个整数 $n, m, p$。

• $1 \le n \le 10^6$
• $2 \le p < m \le 30000$
• $m$ 和 $p$ 是质数。

输出格式

请输出冲突对的数量模 $10^6 + 3$ 的值。

样例

输入样例 1

1 3 2

输出样例 1

100

输入样例 2

2 3 2

输出样例 2

75825

输入样例 3

21 13 5

输出样例 3

142108

输入样例 4

50216 9973 131

输出样例 4

405787