Problem Description

Angie likes playing with variables.

Today, she has prepared three variables $ x, y, z $ and decided to play with them. The three variables are initialized to $ 0 $.

Angie plans to repeat one of the following operations $ n $ times:

• Choose one variable and either increase or decrease its value by $ 1 $.
• Increase or decrease the value of all three variables by $ 1 $.

After $ n $ operations, Angie will be satisfied if the remainder of $ x, y, z $ when divided by $ m $ is $ p, q, r $ respectively.

Angie is interested in how many different sequences of $ n $ operations can satisfy her. For her, count the number of such sequences and output the result modulo $ 998244353 $.

Two sequences of operations are considered different if there exists an integer $i\ (1 \leq i \leq n)$ such that after the $ i $-th operation, the value of at least one variable is different.

Input Format

The input is given from the standard input in the following format:

$ n $ $ m $ $ p $ $ q $ $ r $

Output Format

Output the number of sequences of operations that satisfy Angie, modulo $ 998244353 $.

Sample Input and Output

Sample Input #1

1 3 1 2 2

Sample Output #1

0

Sample Input #2

2 3 1 2 2

Sample Output #2

2

Sample Input #3

1000000 4 1 2 3

Sample Output #3

333551635

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq n \leq 10^6$
• $1 \leq m \leq 10^6$
• $0 \leq p, q, r < m$

Sample Explanation 1

It is not possible to perform one operation that increases the value of one variable by $ 1 $ and decreases the values of the other two variables by $ 1 $.

Sample Explanation 2

First, decrease the value of all three variables by $ 1 $. Then, decrease only the value of $ x $ by $ 1 $. This results in $ x = -2 $, $ y = -1 $, $ z = -1 $. The remainders when these are divided by $ 3 $ are $ 1, 2, 2 $ respectively, so Angie is satisfied with this sequence of operations. There are $ 2 $ such sequences that satisfy Angie.

见题面 Input 部分

见题面 Output 部分