题目描述

Toilet-Ares finds a paper on the ground of Scholomance Academy, which says

$G(N)=\\sum_{k_1+k_2+\\cdots+k_t=N} F(p_1^{k_1}p_2^{k_2}\\cdots p_t^{k_t})$

$F(n)=\\sum_{a_1a_2\\cdots a_m=n} \\varphi(a_1)\\varphi(a_2)...\\varphi(a_m)$

Note that $\\varphi(n)$ is the number of positive integer which is smaller than $n$ and co-prime with $n$. In particular $\\varphi(1)=1$.

Now Toilet-Ares wonders, when given $N,t,m$​ and $p_1,\\ldots,p_t$​, what the value of $G(N)$ modulo $998244353$ is supposed to be.

Of couse, Toilet-Ares who is phoning you, don't know how to solve this problem. Can you help him calculate the answer?

输入格式

The first line contains three integers $N,t,m$ $(1\\le N\\le 10^9, 1\\le t \\le 10^5, 1\\le m \\le 5)$.

The second line contains $t$ integers $p_1,...,p_t$. It is guaranteed that:

• $p_i$​ is prime for all $1\\le i\\le t$;
• $p_i\ e p_j$ for all $i \ e j$;
• $1\\le p_i\\le 10^5$.

输出格式

Output a single integer representing the answer.

样例

1 3 1 
2 3 5

7

2 3 1 
2 3 5

42

25 2 5 
37 101

25 2 5 
37 101

提示

来自:2021牛客暑期多校训练营8

搬运by FrankOu