E - Functional Graph Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MiB

配点 : 2000 点

問題文

整数 N,C,K が与えられます． 長さ N の整数列 x=(x_1,x_2,\ldots,x_N) であって，以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください．

  • 1 \leq x_i \leq N (1 \leq i \leq N)
  • 1 から N までの番号がついた N 頂点からなる無向グラフを考える． このグラフには N 本の辺があり，i 番目の辺は頂点 i と頂点 x_i を結ぶものとする． このとき，グラフの連結成分の個数がちょうど C である．
  • i<x_i を満たす i の個数がちょうど K である．

制約

  • 1 \leq N \leq 250000
  • 1 \leq C \leq N
  • 0 \leq K \leq N-1
  • 入力はすべて整数

入力

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

N C K

出力

答えを出力せよ．

入力例 1

3 1 2

出力例 1

6

条件を満たす x は以下の 6 つです．

  • x=(2,3,1)
  • x=(2,3,2)
  • x=(2,3,3)
  • x=(3,3,1)
  • x=(3,3,2)
  • x=(3,3,3)

入力例 2

3 2 2

出力例 2

0

入力例 3

6 3 0

出力例 3

225

入力例 4

20 4 7

出力例 4

476087626

入力例 5

250000 2025 125000

出力例 5

410390562

Score : 2000 points

Problem Statement

You are given integers N, C, and K. Find the number, modulo 998244353, of length-N integer sequences x=(x_1,x_2,\ldots,x_N) satisfying the following conditions.

  • 1 \leq x_i \leq N (1 \leq i \leq N).
  • Consider an undirected graph with N vertices numbered from 1 to N. This graph has N edges, and the i-th edge connects vertices i and x_i. Then, the number of connected components of the graph is exactly C.
  • The number of i satisfying i<x_i is exactly K.

Constraints

  • 1 \leq N \leq 250000
  • 1 \leq C \leq N
  • 0 \leq K \leq N-1
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N C K

Output

Output the answer.

Sample Input 1

3 1 2

Sample Output 1

6

The following six sequences x satisfy the conditions:

  • x=(2,3,1)
  • x=(2,3,2)
  • x=(2,3,3)
  • x=(3,3,1)
  • x=(3,3,2)
  • x=(3,3,3)

Sample Input 2

3 2 2

Sample Output 2

0

Sample Input 3

6 3 0

Sample Output 3

225

Sample Input 4

20 4 7

Sample Output 4

476087626

Sample Input 5

250000 2025 125000

Sample Output 5

410390562