E - Pair of Permutations 解説 /

実行時間制限: 8 sec / メモリ制限: 1024 MiB

配点 : 1200 点

問題文

(1,2,\dots,N) の順列の組 (P,Q)=((P_1,P_2,\dots,P_N),(Q_1,Q_2,\dots,Q_N)) であって、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

  • 1 \le i \le N を満たす全ての整数 i に対して P_i \le i+M,Q_i \le i+M,P_i \neq Q_i を全て満たす。

制約

  • 2 \le N \le 10^9
  • 1 \le M \le 125000
  • 入力される値は全て整数

入力

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

N M

出力

答えを出力せよ。

入力例 1

3 1

出力例 1

4

(P,Q) として条件を満たすものは、以下の 4 通りです。

  • P = (1,2,3),Q = (2,3,1)
  • P = (1,3,2),Q = (2,1,3)
  • P = (2,3,1),Q = (1,2,3)
  • P = (2,1,3),Q = (1,3,2)

入力例 2

7 3

出力例 2

644544

入力例 3

1000000000 125000

出力例 3

357543611

Score : 1200 points

Problem Statement

Find the number, modulo 998244353, of pairs of permutations (P,Q)=((P_1,P_2,\dots,P_N),(Q_1,Q_2,\dots,Q_N)) of (1,2,\dots,N) satisfying the following condition.

  • P_i \le i+M, Q_i \le i+M, and P_i \neq Q_i all hold for every integer i satisfying 1 \le i \le N.

Constraints

  • 2 \le N \le 10^9
  • 1 \le M \le 125000
  • All input values are integers.

Input

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

N M

Output

Output the answer.

Sample Input 1

3 1

Sample Output 1

4

The pairs (P,Q) satisfying the condition are the following four pairs.

  • P = (1,2,3),Q = (2,3,1)
  • P = (1,3,2),Q = (2,1,3)
  • P = (2,3,1),Q = (1,2,3)
  • P = (2,1,3),Q = (1,3,2)

Sample Input 2

7 3

Sample Output 2

644544

Sample Input 3

1000000000 125000

Sample Output 3

357543611