ZYB loves product

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

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$

The first line has an integer ans

7 11533797
3
2 3
3 1
5 3

278603765

BestCoder Round #44