P15667 [ICPC 2025 Jakarta R] Predisposed

You are given two integers $N$ and $M$. You are also given $Q$ constraints in the form $(X_j, Y_j)$. A sequence $A = (A_1, \dots, A_N)$ of length $N$ is $\textit{predisposed}$ if and only if: - For each $1 \le i \le N$, it holds that $0 \le A_i < M$. - For each $1 \le j \le Q$, the sum of all $A_k$ where $k$ is a multiple of $X_j$ is equal to $Y_j$ under modulo $M$. Formally, $\sum_{X_j \vert k} A_k \equiv Y_j \pmod{M}$. Find the number of all possible predisposed sequences. As the answer can be quite large, compute it modulo $998\;244\;353$.

The first line contains three integers $N$, $M$, and $Q$ ($1 \leq N, M < 998\;244\;353$; $1 \leq Q \leq \min(N, 100\;000)$). Each of the next $Q$ lines contains two integers $X_j$ and $Y_j$ ($1 \leq X_j \leq N$; $0 \leq Y_j < M$; $X_p \neq X_q$ for $p \neq q$) representing a constraint.

Output an integer in a single line representing the number of predisposed sequences modulo $998\;244\;353$.

$\textit{Explanation of Sample 1:}$ The only predisposed sequence is $A = (2, 1)$.