给定两个整数 $N$ 和 $M$。同时给定 $Q$ 个形如 $(X_j, Y_j)$ 的约束。 一个长度为 $N$ 的序列 $A = (A_1, \dots, A_N)$ 被称为“预设的”（predisposed），当且仅当：

• 对于每个 $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 | k} A_k \equiv Y_j \pmod M$。

求所有可能的预设序列的数量。由于答案可能非常大，请将其对 $998\,244\,353$ 取模。

输入格式

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

输出格式

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

样例

输入 1

2 3 2
1 0
2 1

输出 1

1

说明 1

唯一的预设序列是 $A = (2, 1)$。

输入 2

100000 100000 1
100000 0

输出 2

373304036