H-Scholomance Academy_2021牛客暑期多校训练营8

时间限制：C/C++/Rust/Pascal 10秒，其他语言20秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

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  .

The second line contains  integers . It is guaranteed that:
   ·  is prime for all ;
   ·  for all ;
   · .

输出描述:

Output a single integer representing the answer.

示例1

输入

复制

1 3 1
2 3 5

输出

复制

示例2

输入

复制

2 3 1
2 3 5

输出

复制

示例3

输入

复制

25 2 5
37 101

输出

复制

910464559