说明

给定两个整数 $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$ 取模的结果。

2 3 2
1 0
2 1

1

100000 100000 1
100000 0

373304036

提示

样例 1 解释： 唯一的预置序列是 $A = (2, 1)$。

翻译由 DeepSeek V3.2 完成