35178번 - 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 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 $998244353$.

The first line contains three integers $N$, $M$, and $Q$ ($1 \leq N, M < 998244353$; $1 \leq Q \leq \min(N, 100000)$). 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 $998244353$.