题目描述

您有一个无限大的集合，其中有所有小于等于 $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$ 取模。

2 2

998244352

114514 2

662314206

提示

$k$ 的限制如下：

$k=0:$ 选出的集合 $S$ 中至少含有一个完全平方数。

$k=1:$ 选出的集合 $S$ 中只能含有质数。

$k=2:$ 无任何限制。

测试点编号	$n$	$k$
$1\sim 2$	$\leq 5$	$2$
$3\sim 5$	$\leq 20$
$6\sim 11$	$\leq 5000$
$12$	$\leq 10^6$	$0$
$13\sim 14$		$1$
$15\sim 16$	$\leq 10^5$	$2$
$17\sim 20$	$\leq 10^6$

样例 $1$ 解释：

答案为 $\mu(2)\varphi(2)=-1\times 1=-1$，对 $998244353$ 取模为 $998244352$。