Problem Description

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 Format

Input one line containing a positive integer $n$.

Output Format

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.

2

4
1

7

166374067
539688692

Hint

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

For $100\%$ of the testdata, $2\leq n\leq10^4$.

Translated by ChatGPT 5