ZYB loves product

ZYB喜欢研究因数分解.他定义一个数$n$的的$m$分解为一个正整数数列$A_1,A_2...A_m$，满足$n=\prod_{i=1}^{m}A_i$，两种分解A,B不同当且仅当存在一个数字$i$使得$A_i\neq B_i$，也就是说，2=1*2和2=2*1是两种不同的分解方式
我们定义一个数$x$的权值$V(x)=\sum_{d|x}d^k$，其中$k$是一个常数
然后我们定义一个数$n$的$m$分解A的权值为$\prod_{i=1}^{m}V(A_i)$
现在给定$n$,$k$,$m$。求所有$n$的$m$分解的权值和
由于答案奇大无比，你只需要输出答案对998244353取模的值即可
n将会以一种特别的方式读入，具体见输入描述

第一行两个正整数$m$,$k$
第二行一个数$f$。
接下来$f$行，第$i$行两个非负整数$a_i,p_i$
我们定义$n=\prod_{i=1}^{f}a_i^{p_i}$
保证$a_i$是质数且互不相等
$1\leq m,k\leq 10^9$,$1\leq f \leq 5$,$2\leq a_i\leq 10^9$,$1\leq p_i \leq 10000$

一个非负整数，表示答案对998244353取模的值

7 11533797
3
2 3
3 1
5 3

278603765