AT_agc025_b [AGC025B] RGB Coloring

[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

N/A

### 制約 - $ 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 $ になります。