题目描述

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$.

2 3 2
1 0
2 1

1

100000 100000 1
100000 0

373304036

提示

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