/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
高橋君は A 株のリンゴの苗、 B 株のバナナの苗、C 株のサクランボの苗を持っています。同じ種類の苗は区別できません。
N 園の庭を持っている高橋君は、次の条件をすべて満たすように持っている苗を植えることにしました。
- すべての庭に少なくとも 1 株以上の苗を植える。
- 1 つの庭に同じ種類の果物の苗を 2 株以上植えてはいけない。
- 持っているすべての苗を植える必要はない。
条件を満たす植え方は何通りありますか？答えを 998244353 で割ったあまりを求めてください。
ただし、植え方が異なるとは、ある庭が存在して、片方の植え方でその庭に植えられた果物の苗の集合がもう片方と異なることをいいます。
制約
- 1 \leq N \leq 5 \times 10^6
- 0 \leq A \leq N
- 0 \leq B \leq N
- 0 \leq C \leq N
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A B C
出力
答えを出力せよ。
入力例 1
2 2 1 1
出力例 1
21
条件を満たす植え方は 21 通りあり、図示すると以下のようになります。
(縦に並んだ 2 つの枠が庭で、A,B,C はそれぞれリンゴの苗、バナナの苗、サクランボの苗を意味しています。)
入力例 2
2 0 0 0
出力例 2
0
条件を満たす植え方が存在しない場合もあります。
入力例 3
2 0 2 2
出力例 3
9
入力例 4
100 12 34 56
出力例 4
769445780
入力例 5
5000000 2521993 2967363 3802088
出力例 5
264705492
Score : 600 points
Problem Statement
Takahashi has A apple seedlings, B banana seedlings, and C cherry seedlings. Seedlings of the same kind cannot be distinguished.
He will plant these seedlings in his N gardens so that all of the following conditions are satisfied.
- At least one seedling must be planted in every garden.
- It is not allowed to plant two or more seedlings of the same kind in the same garden.
- It is not necessary to plant all seedlings he has.
How many ways are there to plant seedlings to satisfy the conditions? Find the count modulo 998244353.
Two ways are distinguished when there is a garden with different sets of seedlings planted in these two ways.
Constraints
- 1 \leq N \leq 5 \times 10^6
- 0 \leq A \leq N
- 0 \leq B \leq N
- 0 \leq C \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B C
Output
Print the answer.
Sample Input 1
2 2 1 1
Sample Output 1
21
As illustrated below, there are 21 ways to plant seedlings to satisfy the conditions.
(The two frames arranged vertically are the gardens. A, B, C stand for apple, banana, cherry, respectively.)
Sample Input 2
2 0 0 0
Sample Output 2
0
There may be no way to plant seedlings to satisfy the conditions.
Sample Input 3
2 0 2 2
Sample Output 3
9
Sample Input 4
100 12 34 56
Sample Output 4
769445780
Sample Input 5
5000000 2521993 2967363 3802088
Sample Output 5
264705492