ZYB loves product very much.He defines the $m-product$ of $n$ is an array $A_1,A_2...A_m$.This array must satisfied $n=\prod_{i=1}^{m}A_i$
Two m-products A and B are different.If there exists an integer i and $A_i \neq B_i$.
So 2=1\*2 and 2=2\*1 are different
We defines the value of an integer $x$ $V(x)=\sum_{d|x}d^k$
Now we defines the value of an $m-product$ A is $\prod_{i=1}^{m}V(A_i)$
ZYB gives you $n$,$k$ and $m$.He wants to know the sum value of all $m-product$ of $n$
Answer may be very large, output the answer modular 998244353 instead.
n will be given by a special way, please read the Input for detail
Input
The first line has two integers $m$ and $k$
The second line has an integer $f$
The next $f$ lines have two integers $a_i$ and $p_i$
We define $n=\prod_{i=1}^{f}a_i^{p_i}$
Each of $a_i$ is a prime and any two $a_i$ are different
$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$
