Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
アンジェは変数で遊ぶのが好きです。
今日は 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
入力
入力は以下の形式で標準入力から与えられる。
n m p q r
出力
アンジェが満足するような操作列の種類数を 998244353 で割った余りを出力せよ。
入力例 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