Catastrophic Roulette

AtCoder

IDarc174_c

Time2000ms

Memory256MB

Difficulty—

There is a roulette that produces an integer from $1,2,\dots,N$ with equal probability. Two players use it to play the following game: * The players take turns spinning the roulette. * If the produced integer has not appeared before, nothing happens. * Otherwise, the player who spun the roulette pays a fine of $1$ yen. * The game immediately ends when all of the $N$ integers have appeared at least once. For each of the first and second players, find the expected value of the amount of the fine paid before the game ends, modulo $998244353$. On expected values modulo $998244353$It can be proved that the expected values sought in this problem are always rational numbers. Furthermore, under the constraints of this problem, when the expected values are expressed as irreducible fractions $\frac{y}{x}$, it is guaranteed that $x$ is not divisible by $998244353$. Now, there is a unique integer $z$ between $0$ and $998244352$, inclusive, such that $xz \equiv y \pmod{998244353}$. Provide this $z$ as the answer. ## Constraints * $N$ is an integer such that $1 \le N \le 10^6$. ## Input The input is given from Standard Input in the following format: $N$ [samples]

Samples

Input #1

Output #1

0 0

In this input, $N=1$.  
When the first player spins the roulette, it always produces $1$, ending the game immediately.  
Thus, the expected values of the amounts of the fines paid by the first and second players are both $0$.

Input #2

Output #2

332748118 665496236

In this input, $N=2$. Here is a possible progression of the game:

*   The first player spins the roulette, and it produces $2$. Nothing happens.
*   The second player spins the roulette, and it produces $2$. The second player pays a fine of $1$ yen.
*   The first player spins the roulette, and it produces $2$. The first player pays a fine of $1$ yen.
*   The second player spins the roulette, and it produces $1$. Nothing happens.
*   At this point, both $1$ and $2$ have appeared at least once, so the game immediately ends.
*   In this progression, the amount of the fine paid by the first player is $1$ yen, and the amount of the fine paid by the second player is also $1$ yen.

It can be shown that the expected value of the amount of the fine paid by the first player is $\frac{1}{3}$ yen, and the expected value of the amount of the fine paid by the second player is $\frac{2}{3}$ yen.

Input #3

Output #3

174692763 324429416

API Response (JSON)

{
  "problem": {
    "name": "Catastrophic Roulette",
    "description": {
      "content": "There is a roulette that produces an integer from $1,2,\\dots,N$ with equal probability.   Two players use it to play the following game: *   The players take turns spinning the roulette.     *   If t",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc174_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a roulette that produces an integer from $1,2,\\dots,N$ with equal probability.  \nTwo players use it to play the following game:\n\n*   The players take turns spinning the roulette.\n    *   If t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments