[AGC025B] RGB Coloring

你有$n$个格子排成一排，每个格子可以涂成红、蓝、绿或不涂色，得分分别为$A,B,A + B,0$。求使总得分为$K$的方案数，答案对$998244353$取模

[problemUrl]: https://atcoder.jp/contests/agc025/tasks/agc025_b 高橋君はタワーを $ 1 $ つ持っており、それは $ N $ 個のブロックが縦一列に重なって構成されています。 はじめすべてのブロックは無色ですが、高橋君はいくつかのブロックを赤色、緑色、青色のいずれかの色で塗ることで、 タワーを美しくしようとしています。そこで、高橋君は *タワーの美しさ* を以下のように定義することにしました。 - 各ブロックの得点を、赤色に塗られていれば $ A $ 点、緑色に塗られていれば $ A+B $ 点、青色に塗られていれば $ B $ 点、無色ならば $ 0 $ 点として、 $ N $ 個のブロックの得点の合計をタワーの美しさとする。 ただし、$ A,B $ はあらかじめ与えられる正整数の定数であり、各マスが $ 2 $ つ以上の色で同時に塗られることがないことにも注意してください。 高橋君はタワーの美しさがちょうど $ K $ になるようにブロックを塗ろうと考えています。 そのようにタワーを塗る方法は何通りあるでしょうか。 $ 998244353 $ で割った余りを求めてください。 ただし、$ 2 $ つのタワーを塗る方法が異なるとは、あるブロックが存在し、そのブロックに塗られている色が異なること、もしくは、そのブロックが一方では塗られているが、 他方では無色であることを指します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A $ $ B $ $ K $

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

4 1 2 5

40

2 5 6 0

1

90081 33447 90629 6391049189

577742975

### 制約 - $ 1\ ≦\ N\ ≦\ 3×10^5 $ - $ 1\ ≦\ A,B\ ≦\ 3×10^5 $ - $ 0\ ≦\ K\ ≦\ 18×10^{10} $ - 入力される値は全て整数である ### Sample Explanation 1 この場合、赤色 $ 1 $ つにつき $ 1 $ 点、緑色 $ 1 $ つにつき $ 3 $ 点、青色 $ 1 $ つにつき $ 2 $ 点なので、美しさが $ 5 $ になるのは、 - 緑色 $ 1 $ つ、青色 $ 1 $ つ - 赤色 $ 1 $ つ、青色 $ 2 $ つ - 赤色 $ 2 $ つ、緑色 $ 1 $ つ - 赤色 $ 3 $ つ、青色 $ 1 $ つ のいずれかの場合だけです。よって、求める答えは $ 40 $ になります。 ### Sample Explanation 2 美しさが $ 0 $ であるタワーは、すべてのブロックが無色であるものだけです。よって、答えは $ 1 $ になります。