G - Counting Buildings Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

(1,2,\dots,N) の並び替え P=(P_1,P_2,\dots,P_N) に対し、整数 L(P),R(P) を以下のように定めます。

  • N 個のビルが左右一列に並んでおり、左から i 番目のビルの高さは P_i であるとする。このビルの列を左側から見たときに見えるビルの数を L(P)、右側から見たときに見えるビルの数を R(P) とする。
    より形式的には、L(P) はすべての j<i に対して P_j < P_i を満たす i の個数であり、 R(P) はすべての j > i に対して P_i > P_j を満たす i の個数である。

整数 N,K が与えられます。(1,2,\dots,N) の並び替え P であって、L(P)-R(P)=K となるようなものの個数を 998244353 で割ったあまりを求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • |K| \leq N-1
  • 入力はすべて整数

入力

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

N K

出力

答えを出力せよ。

入力例 1

3 -1

出力例 1

1
  • P=(1,2,3): L(P)-R(P)=3-1=2 です。
  • P=(1,3,2): L(P)-R(P)=2-2=0 です。
  • P=(2,1,3): L(P)-R(P)=2-1=1 です。
  • P=(2,3,1): L(P)-R(P)=2-2=0 です。
  • P=(3,1,2): L(P)-R(P)=1-2=-1 です。
  • P=(3,2,1): L(P)-R(P)=1-3=-2 です。

よって、L(P)-R(P)=-1 となる P の個数は 1 です。

入力例 2

1 0

出力例 2

1

入力例 3

2024 385

出力例 3

576300012

998244353 で割ったあまりを出力してください。

Score : 600 points

Problem Statement

For a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N), define integers L(P) and R(P) as follows:

  • Consider N buildings arranged in a row from left to right, with the height of the i-th building from the left being P_i. Then L(P) is the number of buildings visible when viewed from the left, and R(P) is the number of buildings visible when viewed from the right.
    More formally, L(P) is the count of indices i such that P_j < P_i for all j < i, and R(P) is the count of indices i such that P_i > P_j for all j > i.

You are given integers N and K. Find, modulo 998244353, the count of all permutations P of (1,2,\dots,N) such that L(P)-R(P)=K.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • |K| \leq N-1
  • All input values are integers.

Input

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

N K

Output

Print the answer.

Sample Input 1

3 -1

Sample Output 1

1
  • P=(1,2,3): L(P)-R(P)=3-1=2.
  • P=(1,3,2): L(P)-R(P)=2-2=0.
  • P=(2,1,3): L(P)-R(P)=2-1=1.
  • P=(2,3,1): L(P)-R(P)=2-2=0.
  • P=(3,1,2): L(P)-R(P)=1-2=-1.
  • P=(3,2,1): L(P)-R(P)=1-3=-2.

Therefore, the number of permutations P with L(P)-R(P)=-1 is 1.

Sample Input 2

1 0

Sample Output 2

1

Sample Input 3

2024 385

Sample Output 3

576300012

Print the count modulo 998244353.