/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 2200 点
問題文
数直線上に，区別できない 2 つの駒が置かれています． どちらの駒も最初，座標 0 にあります．（駒は同じ座標に同時に存在できます）
これらの駒に対して，以下の 2 種類の操作が可能です．
- 好きな駒を 1 つ選び，1 大きい座標に移動する．
- 座標の小さい駒を，座標の大きい駒の位置へと移動する． なお，もともと 2 つの駒が同じ座標に置いてある場合は何も起きないが，その場合でも 1 回の操作として数える．
以上の操作を好きな順番で N 回繰り返して，2 つの駒の一方が座標 A，他方が座標 B にあるようにしたいです． このような動かし方が何通りあるかを求めてください． ただし答えは非常に大きくなることがあるので，998244353 で割ったあまりを求めてください．
なお，ある 2 つの動かし方 x,y が異なるとは，整数 i (1 \leq i \leq N) であって， ( 動かし方 x で i 回目の操作後に駒の置いてある座標の集合 ) と ( 動かし方 y で i 回目の操作後に駒の置いてある座標の集合 ) が異なるものが存在することを意味します．
制約
- 1 \leq N \leq 10^7
- 0 \leq A \leq B \leq N
- 入力される値はすべて整数である．
入力
入力は以下の形式で標準入力から与えられる．
N A B
出力
条件をみたす駒の動かし方が何通りあるかを 998244353 で割ったあまりを出力せよ．
入力例 1
5 1 3
出力例 1
4
以下の 4 通りの動かし方があります． なお，(x,y) で，駒の座標がそれぞれ x,y にある状態を表しています．
- (0,0)→(0,0)→(0,1)→(0,2)→(0,3)→(1,3)
- (0,0)→(0,0)→(0,1)→(0,2)→(1,2)→(1,3)
- (0,0)→(0,0)→(0,1)→(1,1)→(1,2)→(1,3)
- (0,0)→(0,1)→(1,1)→(1,1)→(1,2)→(1,3)
入力例 2
10 0 0
出力例 2
1
入力例 3
10 4 6
出力例 3
197
入力例 4
1000000 100000 200000
出力例 4
758840509
Score : 2200 points
Problem Statement
We have two indistinguishable pieces placed on a number line. Both pieces are initially at coordinate 0. (They can occupy the same position.)
We can do the following two kinds of operations:
- Choose a piece and move it to the right (the positive direction) by 1.
- Move the piece with the smaller coordinate to the position of the piece with the greater coordinate. If two pieces already occupy the same position, nothing happens, but it still counts as doing one operation.
We want to do a total of N operations of these kinds in some order so that one of the pieces will be at coordinate A and the other at coordinate B. Find the number of ways to move the pieces to achieve it. The answer can be enormous, so compute the count modulo 998244353.
Two ways to move the pieces are considered different if and only if there exists an integer i (1 \leq i \leq N) such that the set of the coordinates occupied by the pieces after the i-th operation is different in those two ways.
Constraints
- 1 \leq N \leq 10^7
- 0 \leq A \leq B \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B
Output
Print the number of ways to move the pieces to achieve our objective, modulo 998244353.
Sample Input 1
5 1 3
Sample Output 1
4
Shown below are the four ways to move the pieces, where (x,y) represents the state where the two pieces are at coordinates x and y.
- (0,0)→(0,0)→(0,1)→(0,2)→(0,3)→(1,3)
- (0,0)→(0,0)→(0,1)→(0,2)→(1,2)→(1,3)
- (0,0)→(0,0)→(0,1)→(1,1)→(1,2)→(1,3)
- (0,0)→(0,1)→(1,1)→(1,1)→(1,2)→(1,3)
Sample Input 2
10 0 0
Sample Output 2
1
Sample Input 3
10 4 6
Sample Output 3
197
Sample Input 4
1000000 100000 200000
Sample Output 4
758840509