P7092 计数题

您有一个无限大的集合，其中有所有小于等于 $n$ 的质数和其中它们的乘积。 如 $n=5$，集合中实际包含的数为 $2,3,5$（质数），$4,6,8,9,10,12.....$（质数之积），假设这个集合为 $T$。 求： $\sum\limits_{S\subset T,S\neq\varnothing}\mu(\prod\limits_{i\in S}i)\varphi(\prod\limits_{i\in S}i)$ 对 $998244353$ 取模。可以证明这个和是存在的。 为了您能更好的获得部分分，我们会给定一个 $k$，表示一些限制，**$k$ 的值可能影响答案！请认真阅读提示说明**。 $n\leq 10^6$

一行两个整数 $n,k$。

一行一个整数，表示答案，对 $998244353$ 取模。

$k$ 的限制如下： $k=0:$ 选出的集合 $S$ 中至少含有一个完全平方数。 $k=1:$ 选出的集合 $S$ 中只能含有质数。 $k=2:$ 无任何限制。 | 测试点编号 |$n$ |$k$ | | :----------: | :----------: | :----------: | | $1\sim 2$ |$\leq 5$ |$2$ | | $3\sim 5$ |$\leq 20$ |$2$ | | $6\sim 11$ |$\leq 5000$ |$2$ | | $12$ |$\leq 10^6$ |$0$ | | $13\sim 14$ |$\leq 10^6$ |$1$ | | $15\sim 16$ |$\leq 10^5$ |$2$ | | $17\sim 20$ |$\leq 10^6$ |$2$ | 样例 $1$ 解释： 答案为 $\mu(2)\varphi(2)=-1\times 1=-1$，对 $998244353$ 取模为 $998244352$。