B - RGB Coloring Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

高橋君はタワーを 1 つ持っており、それは N 個のブロックが縦一列に重なって構成されています。 はじめすべてのブロックは無色ですが、高橋君はいくつかのブロックを赤色、緑色、青色のいずれかの色で塗ることで、 タワーを美しくしようとしています。そこで、高橋君は タワーの美しさ を以下のように定義することにしました。

  • 各ブロックの得点を、赤色に塗られていれば A 点、緑色に塗られていれば A+B 点、青色に塗られていれば B 点、無色ならば 0 点として、 N 個のブロックの得点の合計をタワーの美しさとする。

ただし、A,B はあらかじめ与えられる正整数の定数であり、各マスが 2 つ以上の色で同時に塗られることがないことにも注意してください。

高橋君はタワーの美しさがちょうど K になるようにブロックを塗ろうと考えています。 そのようにタワーを塗る方法は何通りあるでしょうか。 998244353 で割った余りを求めてください。 ただし、2 つのタワーを塗る方法が異なるとは、あるブロックが存在し、そのブロックに塗られている色が異なること、もしくは、そのブロックが一方では塗られているが、 他方では無色であることを指します。

制約

  • 1 ≦ N ≦ 3×10^5
  • 1 ≦ A,B ≦ 3×10^5
  • 0 ≦ K ≦ 18×10^{10}
  • 入力される値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N A B K

出力

タワーを塗る方法の個数を 998244353 で割った余りを出力せよ。

入力例 1

4 1 2 5

出力例 1

40

この場合、赤色 1 つにつき 1 点、緑色 1 つにつき 3 点、青色 1 つにつき 2 点なので、美しさが 5 になるのは、

  • 緑色 1 つ、青色 1 つ
  • 赤色 1 つ、青色 2 つ
  • 赤色 2 つ、緑色 1 つ
  • 赤色 3 つ、青色 1 つ

のいずれかの場合だけです。よって、求める答えは 40 になります。

入力例 2

2 5 6 0

出力例 2

1

美しさが 0 であるタワーは、すべてのブロックが無色であるものだけです。よって、答えは 1 になります。

入力例 3

90081 33447 90629 6391049189

出力例 3

577742975

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 ≤ 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

Output

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

Sample Input 1

4 1 2 5

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

Sample Input 2

2 5 6 0

Sample Output 2

1

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

Sample Input 3

90081 33447 90629 6391049189

Sample Output 3

577742975