当前没有测试数据。

乘积取模2

得分：600分

问题描述

在长度为$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$

输出

输出答案。

2 3 6

5

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

10 0 2

1023

1000000000 20220326 1000000000000

561382653

请务必对$998244353$取模。