Description

You have an infinite set that contains all primes less than or equal to $n$, and also all products made from these primes.

For example, when $n=5$, the set actually contains $2,3,5$ (primes), and $4,6,8,9,10,12\ldots$ (products of primes). Let this set be $T$.

Compute:

$\sum\limits_{S\subset T,S\neq\varnothing}\mu(\prod\limits_{i\in S}i)\varphi(\prod\limits_{i\in S}i)$

Take the result modulo $998244353$. It can be proven that this sum exists.

To help you get partial scores, we will give an integer $k$ that represents some restrictions. The value of $k$ may affect the answer. Please read the hint carefully.

$n\leq 10^6$.

Input Format

One line with two integers $n,k$.

Output Format

One line with one integer, the answer modulo $998244353$.

2 2

998244352

114514 2

662314206

Hint

The restrictions for $k$ are as follows:

$k=0:$ The chosen set $S$ must contain at least one perfect square.

$k=1:$ The chosen set $S$ can only contain primes.

$k=2:$ No restrictions.

Explanation for Sample $1$:

The answer is $\mu(2)\varphi(2)=-1\times 1=-1$, which is $998244352$ modulo $998244353$.

Translated by ChatGPT 5