問題文

Alice と Bob と Chris はこれから N 回じゃんけんをします。 ただし、各々が出す手には次のような制限があります。

• Alice は グー をちょうど A_R 回、 パー をちょうど A_P 回、 チョキ をちょうど A_S 回 出す。
• Bob は グー をちょうど B_R 回、 パー をちょうど B_P 回、 チョキ をちょうど B_S 回 出す。
• Chris は グー をちょうど C_R 回、 パー をちょうど C_P 回、 チョキ をちょうど C_S 回 出す。

Alice と Bob と Chris はとても仲良しなので、 N 回すべてで あいこ になるようにしたいです。 N 回のじゃんけんにわたる 3 人の手の出し方であってこれを達成する方法の数を 998244353 で割ったあまりを求めてください。

制約

• 入力はすべて整数
• 1\le N\le 1.5\times 10^{6}
• 0\le A_R,A_P,A_S,B_R,B_P,B_S,C_R,C_P,C_S\le 1.5\times 10^{6}
• A_R+A_P+A_S=B_R+B_P+B_S=C_R+C_P+C_S=N

入力例 1

2
2 0 0 1 1 0 1 0 1

出力例 1

2

じゃんけんを 2 回行います。Alice は 2 回とも グー を出します。Bobが グー を出すときにChrisも グー を出せば 2 回ともあいこになります。Bobが 1 回目に グー を出すか 2 回目に グー を出すかの 2 通りが 2 回ともあいこになる方法として考えられます。

入力例 2

3
0 1 2 3 0 0 1 1 1

出力例 2

0

残念ながら、3 回すべてのじゃんけんであいこにすることはできません。

入力例 3

333333
111111 111111 111111 111111 111111 111111 111111 111111 111111

出力例 3

383902959