問題文

アンジェは変数で遊ぶのが好きです。

今日は 3 つの変数 x,~y,~z を用意して、これらを使って遊ぶことにしました。 3 つの変数は 0 で初期化されています。

アンジェは、これらの変数に対して、以下の操作のいずれかを選んで行うことを n 回繰り返すつもりです。

• 変数を 1 つ選ぶ。その変数の値を 1 増やす、もしくは 1 減らす。
• 3 つの変数全ての値を 1 ずつ増やす、もしくは 1 ずつ減らす。

n 回の操作を行ったあとに、x,~y,~z を m で割った余りがそれぞれ p,~q,~r であるとき、 アンジェは満足します。

アンジェは、自分が満足できるような n 回の操作列が何種類あるのかに興味を持ちました。 彼女の代わりに、そのような操作列の種類数を数えて、998244353 で割った余りを出力してください。

ここで 2 つの操作列は、ある整数 i\ (1 \leq i \leq n) が存在して、i 回目の操作後に 1 つ以上の変数の値が異なるとき、別の種類であるとみなします。

制約

• 入力は全て整数である。
• 1 \leq n \leq 10^6
• 1 \leq m \leq 10^6
• 0 \leq p,\ q,\ r < m

入力例 1

1 3 1 2 2

出力例 1

0

1 回の操作で、ある 1 つの変数の値だけを 1 増やし、残り 2 つの変数の値を 1 減らすことはできません。

入力例 2

2 3 1 2 2

出力例 2

2

まず、3 つすべての変数の値を 1 減らします。次に x の値だけを 1 減らすことで、x の値は -2、 y の値は -1、z の値は -1 になります。 これらを 3 で割った余りはそれぞれ 1,~2,~2 であるため、アンジェはこの操作列に満足します。

アンジェが満足する操作列は、この操作列を含めて 2 種類あります。

入力例 3

1000000 4 1 2 3

出力例 3

333551635