P7092 Counting Problem.

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$.

One line with two integers $n,k$.

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

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. | Test Point ID | $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$ | Explanation for Sample $1$: The answer is $\mu(2)\varphi(2)=-1\times 1=-1$, which is $998244352$ modulo $998244353$. Translated by ChatGPT 5