配点 : $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$

出力

答えを出力せよ。

2 2 1 1

21

条件を満たす植え方は $21$ 通りあり、図示すると以下のようになります。 (縦に並んだ $2$ つの枠が庭で、$A,B,C$ はそれぞれリンゴの苗、バナナの苗、サクランボの苗を意味しています。)

2 0 0 0

0

条件を満たす植え方が存在しない場合もあります。

2 0 2 2

9

100 12 34 56

769445780

5000000 2521993 2967363 3802088

264705492