问题陈述

在长度为 $K$ 的整数序列 $A=(A_1, \\ldots, A_K)$ 中，有多少个满足以下所有条件的序列？
计算结果对 $998244353$ 取模。

• 对于每个 $i(1\\leq i\\leq K)$，有 $0\\leq A_i \\leq M-1$。

• $\\displaystyle\\prod_{i=1}^{K} A_i \\equiv N \\pmod M$。

约束条件

• $1 \\leq K \\leq 10^9$
• $0 \\leq N \\lt M \\leq 10^{12}$
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入给出：

$K$ $N$ $M$

输出

输出答案。

示例输入 1

2 3 6

示例输出 1

5

满足条件的五个序列 $A$ 是 $(1,3),(3,1),(3,3),(3,5),(5,3)$。

示例输入 2

10 0 2

示例输出 2

1023

示例输入 3

1000000000 20220326 1000000000000

示例输出 3

561382653

请务必对 $998244353$ 取模。