/ 
Time Limit: 10 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
(1,2,\dots,N) の順列 P を用意して、次の操作を行います。
N 枚のカードがあります。これらのカードには 1 から N の番号がついてます。カード i には P_i が書かれています。
整数 X=1 があります。はじめ PCT 君は何も持っていません。PCT 君は以下の操作を i=1,2,\dots,N の順で行います。
- カード i を手に入れる。その後、X が書かれたカードを持っている限り以下の行動を繰り返す。
- X の書かれているカードを食べ、X を 1 増やす。
- 現在持っているカードの枚数が M 枚以上の場合、持っているカードを全て捨てて操作を終了する。これ以降も操作は行わない。
ここで、以下のように順列 P のスコアを定義します。
- カードが捨てられて操作が終わった場合、P のスコアを 0 とする。
- カードが捨てられずに操作が最後まで行われた場合、P のスコアを \prod_{i=1}^{N-1} (i 回目の操作終了時に PCT 君が持っているカードの枚数 ) とする。
P としてあり得るものは N! 通りありますが、そのすべてに対してスコアの総和を 998244353 で割ったあまりを出力してください。
制約
- 2 \le N \le 2 \times 10^5
- 2 \le M \le N
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
3 2
出力例 1
1
P=(3,1,2) の場合、以下のように操作が行われます。
- 1 回目の操作
- PCT 君がカード 1 を手に入れる。
- 現在持っているカードの枚数は 1 枚なので、操作を続行する。
- 2 回目の操作
- PCT 君がカード 2 を手に入れる。
- カード 2 を食べ、X を 2 にする。
- 現在持っているカードの枚数は 1 枚なので、操作を続行する。
- 3 回目の操作
- PCT 君がカード 3 を手に入れる。
- カード 1,3 を食べ、X を 4 にする。
- 現在持っているカードの枚数は 0 枚なので、操作を続行する。
操作が最後まで行われたため、(3,1,2) のスコアは 1 \times 1 = 1 です。
(3,1,2) 以外にスコアが 1 以上になる順列は存在しないため、解は 1 です。
入力例 2
3 3
出力例 2
5
入力例 3
146146 146
出力例 3
103537573
Score : 1200 points
Problem Statement
The following process is carried out on a permutation P of (1,2,\dots,N).
We have N cards, numbered 1 to N. Card i has the integer P_i written on it.
There are an integer X=1 and a boy called PCT, who initially has nothing. PCT does the following procedure for each i=1,2,\dots,N in this order.
- Get Card i. Then, repeat the following action as long as he has a card with X written on it:
- eat the card with X written on it, and then add 1 to X.
- If PCT currently has M or more cards, throw away all cards he has and terminate the process, without performing any more procedures.
Here, let us define the score of the permutation P as follows:
- if the process is terminated by throwing away cards, the score of P is 0;
- if the process is carried out through the end without throwing away cards, the score of P is \prod_{i=1}^{N-1} ( the number of cards PCT has at the end of the i-th procedure ).
There are N! permutations P of (1,2,\dots,N). Find the sum of the scores of all those permutations, modulo 998244353.
Constraints
- 2 \le N \le 2 \times 10^5
- 2 \le M \le N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
3 2
Sample Output 1
1
For P=(3,1,2), the process goes as follows.
- The first procedure:
- PCT gets Card 1.
- PCT currently has 1 card, so he goes on.
- The second procedure:
- PCT gets Card 2.
- PCT eats Card 2 and make X = 2.
- PCT currently has 1 card, so he goes on.
- The third procedure:
- PCT gets Card 3.
- PCT eats Cards 1,3 and make X = 4.
- PCT currently has 0 cards, so he goes on.
The process is carried out through the end, so the score of (3,1,2) is 1 \times 1 = 1.
Other than (3,1,2), there is no permutation with a score of 1 or greater, so the answer is 1.
Sample Input 2
3 3
Sample Output 2
5
Sample Input 3
146146 146
Sample Output 3
103537573