Score : $700$ points

Problem Statement

Takahashi has a tower which is divided into $N$ layers. Initially, all the layers are uncolored. Takahashi is going to paint some of the layers in red, green or blue to make a beautiful tower. He defines the beauty of the tower as follows:

• The beauty of the tower is the sum of the scores of the $N$ layers, where the score of a layer is $A$ if the layer is painted red, $A+B$ if the layer is painted green, $B$ if the layer is painted blue, and $0$ if the layer is uncolored.

Here, $A$ and $B$ are positive integer constants given beforehand. Also note that a layer may not be painted in two or more colors.

Takahashi is planning to paint the tower so that the beauty of the tower becomes exactly $K$. How many such ways are there to paint the tower? Find the count modulo $998244353$. Two ways to paint the tower are considered different when there exists a layer that is painted in different colors, or a layer that is painted in some color in one of the ways and not in the other.

Constraints

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq A,B \leq 3 \times 10^5$
• $0 \leq K \leq 18 \times 10^{10}$
• All values in the input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $A$ $B$ $K$

Output

Print the number of the ways to paint tiles, modulo $998244353$.

4 1 2 5

40

In this case, a red layer worth $1$ points, a green layer worth $3$ points and the blue layer worth $2$ points. The beauty of the tower is $5$ when we have one of the following sets of painted layers:

• $1$ green, $1$ blue
• $1$ red, $2$ blues
• $2$ reds, $1$ green
• $3$ reds, $1$ blue

The total number of the ways to produce them is $40$.

2 5 6 0

1

The beauty of the tower is $0$ only when all the layers are uncolored. Thus, the answer is $1$.

90081 33447 90629 6391049189

577742975