RGB Coloring

AtCoder

IDagc025_b

Time2000ms

Memory256MB

Difficulty—

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 ≤ N ≤ 3×10^5$ * $1 ≤ A,B ≤ 3×10^5$ * $0 ≤ K ≤ 18×10^{10}$ * All values in the input are integers. ## Input Input is given from Standard Input in the following format: $N$ $A$ $B$ $K$ [samples]

Samples

Input #1

4 1 2 5

Output #1

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$.

Input #2

2 5 6 0

Output #2

1

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

Input #3

90081 33447 90629 6391049189

Output #3

577742975

API Response (JSON)

{
  "problem": {
    "name": "RGB Coloring",
    "description": {
      "content": "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 defi",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc025_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 defi...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments