配点 : $700$ 点

問題文

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

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

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

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

制約

• $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}$
• 入力される値は全て整数である

入力

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

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

出力

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

4 1 2 5

40

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

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

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

2 5 6 0

1

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

90081 33447 90629 6391049189

577742975