P15667 [ICPC 2025 Jakarta R] Predisposed

给定两个整数 $N$ 和 $M$，以及 $Q$ 个形式为 $(X_j, Y_j)$ 的约束。 一个长度为 $N$ 的序列 $A = (A_1, \dots, A_N)$ 被称为**预置序列**，当且仅当： - 对于每个 $1 \le i \le N$，有 $0 \le A_i < M$。 - 对于每个 $1 \le j \le Q$，所有满足 $k$ 是 $X_j$ 的倍数的 $A_k$ 之和在模 $M$ 下等于 $Y_j$。形式化地，$\sum_{X_j \vert k} A_k \equiv Y_j \pmod{M}$。 求所有可能的预置序列的数量。由于答案可能很大，请输出其对 $998\;244\;353$ 取模的结果。

第一行包含三个整数 $N$、$M$ 和 $Q$（$1 \leq N, M < 998\;244\;353$；$1 \leq Q \leq \min(N, 100\;000)$）。 接下来的 $Q$ 行，每行包含两个整数 $X_j$ 和 $Y_j$（$1 \leq X_j \leq N$；$0 \leq Y_j < M$；对于 $p \neq q$，有 $X_p \neq X_q$），表示一个约束。

输出一行一个整数，表示预置序列的数量对 $998\;244\;353$ 取模的结果。

**样例 1 解释：** 唯一的预置序列是 $A = (2, 1)$。 翻译由 DeepSeek V3.2 完成