/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
正整数からなる集合が書かれている黒板があります。はじめ、黒板には集合 S=\lbrace 1,2,\dots,A,A+1,A+2,\dots,A+B\rbrace が書き込まれています。
高橋君は以下の操作を N-1 回行って、黒板に書き込まれている集合を N 個にしたいです。
- 黒板に書かれている整数集合の中から、A 以下、 A+1 以上の要素をそれぞれ 1 つ以上持つ集合を 1 つ選ぶ。選んだ集合 S_0 の中から A 以下、 A+1 以上の要素を 1 つずつ選び、それぞれ a,b とする。黒板から集合 S_0 を消し、以下の条件をすべて満たすような 2 つの集合 S_1,S_2 を好きに選んで、黒板に書き込む
- S_1,S_2 の和集合は S_0 であり、共通の要素を持たない
- a \in S_1, b \in S_2
一連の操作の方法として考えられるものの数を 998244353 で割った余りを求めてください。
ただし、一連の操作はある i\ (1 \leq i \leq N-1) であって、 i 回目の操作で選んだ S_0,a,b,S_1,S_2 のいずれかが異なるものが存在するときに区別します。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A,B \leq 2 \times 10^5
- N \leq A+B
- 与えられる入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A B
出力
答えを出力せよ。
入力例 1
3 2 4
出力例 1
1728
操作の一例として以下のようなものが考えられます。
- S_0=\lbrace 1,2,3,4,5,6\rbrace を選び、 a=2,b=5 とし、 S_1 =\lbrace 1,2,3,6\rbrace, S_2=\lbrace 4,5\rbrace とする。黒板に書かれている整数集合は \lbrace 1,2,3,6\rbrace,\lbrace 4,5\rbrace の 2 つになる。
- S_0=\lbrace 1,2,3,6\rbrace を選び、 a=1,b=3 とし、 S_1 = \lbrace1,2\rbrace, S_2=\lbrace 3,6\rbrace とする。黒板に書かれている整数集合は \lbrace 1,2\rbrace,\lbrace 3,6\rbrace,\lbrace 4,5\rbrace の 3 つになる。
入力例 2
4 1 3
出力例 2
6
1 回目の操作で a=1,b=2 とし、 S_1 = \lbrace 1\rbrace,S_2 = \lbrace 2,3,4\rbrace とすると、 2 回目以降の操作ができなくなります。
このように N-1 回操作をやりきらずに操作ができなくなるようなものは数えません。
入力例 3
5 6 6
出力例 3
84486693
入力例 4
173173 173173 173173
出力例 4
446948086
Score: 1200 points
Problem Statement
There is a blackboard with a set of positive integers written on it. Initially, the set S=\lbrace 1,2,\dots,A,A+1,A+2,\dots,A+B\rbrace is written on the blackboard.
Takahashi wants to perform the following operation N-1 times to have N sets on the blackboard:
- From the sets of integers written on the blackboard, choose a set S_0 that contains at least one element not greater than A and at least one element not less than A+1. From the chosen set S_0, choose one element a not greater than A and one element b not less than A+1. Erase the set S_0 from the blackboard and write two sets S_1 and S_2 of his choice that satisfy all of the following conditions:
- The union of S_1 and S_2 is S_0, and they have no common elements.
- a \in S_1, b \in S_2
Find the number of possible ways to perform the series of operations, modulo 998244353.
Here, two series of operations are distinguished when there is an i\ (1 \leq i \leq N-1) such that S_0, a, b, S_1, or S_2 chosen in the i-th operation of one series is different from that of the other series.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A,B \leq 2 \times 10^5
- N \leq A+B
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A B
Output
Print the answer.
Sample Input 1
3 2 4
Sample Output 1
1728
One possible series of operations is as follows:
- Choose S_0=\lbrace 1,2,3,4,5,6\rbrace, let a=2 and b=5, and let S_1 =\lbrace 1,2,3,6\rbrace and S_2=\lbrace 4,5\rbrace. There are now two sets of integers written on the blackboard: \lbrace 1,2,3,6\rbrace and \lbrace 4,5\rbrace.
- Choose S_0=\lbrace 1,2,3,6\rbrace, let a=1 and b=3, and let S_1 = \lbrace1,2\rbrace and S_2=\lbrace 3,6\rbrace. There are now three sets of integers written on the blackboard: \lbrace 1,2\rbrace, \lbrace 3,6\rbrace, and \lbrace 4,5\rbrace.
Sample Input 2
4 1 3
Sample Output 2
6
If we let a=1 and b=2 and let S_1 = \lbrace 1\rbrace and S_2 = \lbrace 2,3,4\rbrace in the first operation, we can no longer perform the second and subsequent operations.
Do not count these cases where we cannot complete N-1 operations.
Sample Input 3
5 6 6
Sample Output 3
84486693
Sample Input 4
173173 173173 173173
Sample Output 4
446948086