L - Permutation 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 4 点

問題文

整数 N が与えられます。 (1, 2, \dots, N) の順列 p = (p_1, p_2, \dots, p_N) であって次の条件を満たすものの個数を 998244353 で割った余りを求めてください。

  • 1 \leq i \leq N を満たす全ての整数 i について p_{p_i} \neq i が成り立つ。

制約

  • 1 \leq N \leq 2.5 \times 10^5
  • N は整数

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを出力せよ。

入力例 1

3

出力例 1

2

条件を満たす順列 p は次の 2 個です。

  • (2,3,1)
  • (3,1,2)

入力例 2

123456

出力例 2

916370671

Score: 4 points

Problem Statement

You are given an integer N.
Consider permutations p = (p_1, p_2, \dots, p_N) of (1, 2, \dots, N).
Count how many such permutations satisfy the following condition, and output the result modulo 998244353.

  • For every integer i such that 1 \leq i \leq N, it must hold that p_{p_i} \neq i.

Constraints

  • 1 \leq N \leq 2.5 \times 10^5
  • N is an integer

Input

The input is given from standard input in the following format:

N

Output

Print the answer.

Sample Input 1

3

Sample Output 1

2

The following 2 permutations p satisfy the condition:

  • (2,3,1)
  • (3,1,2)

Sample Input 2

123456

Sample Output 2

916370671