P7474 "C.E.L.U-02" Academic Spirit

A **one-sentence statement** is provided for reading. There are $n$ children in a place. Each child has a **unique** idea, and the **ID** of the idea owned by the $i$-th child is $i$. The teacher asks each child to randomly draw one card from a set of cards numbered $1 \sim n$. **After drawing, the child puts the card back**, and then the child will **exchange** ideas with the child whose number is on the card (an exchange means that **both** people tell **all** the ideas they know to each other). Since exchanging ideas with oneself may look silly to them, if **the number on the card is the same as their own**, the child will draw again (the card has already been put back at this time), and will keep doing so **until the number is not their own**. Soon, every child has finished drawing once. Each child will use **all** the ideas they have collected to create a contest. Because of the exchange of ideas, many contests are **connected** with each other. If two contests contain problems with the **same** idea, we say these two contests are connected. “Connection” is **transitive**: **if contest $\mathbf A$ and contest $\mathbf B$ are connected, and contest $\mathbf B$ and contest $\mathbf C$ are connected, then contest $\mathbf A$ and contest $\mathbf C$ are also connected**. To avoid misunderstanding, here is an example: Suppose there are only four contests. Contest 1 contains ideas $1$, $2$; contest 2 contains ideas $2$, $5$; contest 3 contains ideas $3$, $5$, $8$; contest 4 contains ideas $4$, $7$. Then contest 1 and contest 2 have a **direct connection**. Although contest 1 and contest 3 have no common idea, they are still **connected**. Contest 4 has no connection with any other contest. All contests that are connected will belong to the same contest set, while contests with no connection belong to different contest sets. In the example above, contests 1, 2, and 3 belong to one contest set, and contest 4 belongs to another. Find the expectation $E_0$ of the **total number of times** everyone draws a card, and the expectation $E_1$ of the number $s$ of contest sets. --- **One-sentence statement:** For each node $i$, randomly connect an undirected edge to a node in $[1,n]$. If it connects to itself, keep the edge and connect again, repeating until it connects to a different node. Find the expectations of the number of edges and the number of connected components.

Input one line containing a positive integer $n$.

Output $E_0$ on the first line, and $E_1$ on the second line. It can be proven that both are **rational numbers**. To avoid precision errors, you only need to output their results modulo the prime $998244353$. If you do not know how to take a fraction modulo a prime, you may look up Fermat’s little theorem and multiplicative inverses. If the output format is wrong or both answers are wrong, you get $0$ points for this test. If only the first question is correct, you get $3$ points. If only the second question is correct, you get $7$ points. If both questions are correct, you get $10$ points. **Be sure to output two integers.**

--- ### Sample Explanation **Sample Explanation 1** - For each child, the probability that the number of draws is $1$ is $\dfrac{1}{2}$, the probability that the number of draws is $2$ is $\dfrac{1}{4}$, and the probability that the number of draws is $i$ is $\dfrac{1}{2^i}$. The expected number of draws is $2$, so the total expected number of draws is $4$. - Child $1$ will definitely exchange ideas with child $2$, so the contests they create must belong to the same contest set. $E_1=1$. **Sample Explanation 2** - The answer to the first question before taking modulo is $\dfrac{49}{6}$. - The answer to the second question before taking modulo is $\dfrac{2245}{1944}$. --- ### Constraints | Test Point ID | $n$ | Test Point ID | $n$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $\leq 3$ | $5$ | $\leq 1000$ | | $2$ | $\leq 5$ | $6$ | $\leq 2000$ | | $3$ | $\leq 9$ | $7\sim8$ | $\leq 5000$ | | $4$ | $\leq 12$ | $9\sim 10$ | $\leq10^4$ | For $100\%$ of the testdata, $2\leq n\leq10^4$. --- Translated by ChatGPT 5