久莲は遊ぶのが大好きな女の子です。

ついに夏休みが来たので、久莲は友達を水泳に招くことにしました。まず、自宅のプライベートビーチの沖に長方形の海域を囲み、泳ぐ場所を作ろうと考えています。しかし、海にはさまざまな危険があり、水深が深すぎる場所や毒のあるクラゲが現れる場所もあります。久莲は、囲んだ海域全体を安全にしたいと思っています。

予備的な分析により、この海域を底辺が $N$ メートル、高さが $1001$ メートルの長方形の格子と見なしました。格子の底辺は自宅のプライベートビーチに対応し、各 $1\times 1$ の小さな正方形が 1 単位の海域を表します。久莲は父親に、明日すべての小さな正方形が安全かどうかを調べてもらうことにしました。その情報が分かれば、いよいよ理想の泳ぐ場所を囲めます。

久莲の理想の水泳場は、次の 3 条件を満たします。

• 安全でなければなりません。すなわち、水泳場に含まれるすべての単位海域が安全です。
• 長方形でなければなりません。すなわち、格子全体の $a\times b$ の部分格子です。
• ビーチに接していなければなりません。すなわち、水泳場の下端が格子の下端にぴったり接しています。

例えば、$N=5$ のとき、測定結果が下図のようになったとします（$1001$ は大きすぎるので、格子の一番下の 3 行の情報だけを示しています。それ以外はすべて危険です）。

この場合、一番下の行にある $1\times 4$ の部分海域や、3 列目の $3\times 1$ の部分海域を選べます。一番上の行の $1\times 5$ の部分海域は、ビーチに接していないので選べないことに注意してください。

友達に楽しんでもらうため、久莲は水泳場の面積をできるだけ大きくしたいと思っています。したがって、一番下の行の $1\times 4$ の部分海域を最終的な案として選びます。

各単位海域が安全かどうか分かるのは明日ですが、久莲は今すぐ、自分の水泳場がどのくらいの面積になるかを見積もりたいと考えています。簡単な見積もりとして、各単位海域はそれぞれ独立に、確率 $q$ で安全、確率 $1-q$ で危険であると仮定します。選べる最大の水泳場の面積がちょうど $K$ になる確率を知りたいのです。

しかし、久莲は数学に興味がないので、この値の計算をあなたに手伝ってもらいたいと思っています。

入力

ファイル pool.in からデータを読み込んでください。

1 行に 4 つの正整数 $N,K,x,y$ が与えられます。ただし、$1\le x<y<998244353$ です。$q$ の値は $\frac{x}{y}$ です。

出力

ファイル pool.out に出力してください。

答えの法 $998244353$ における値を表す整数を、1 行に 1 つ出力してください。

すなわち、答えを既約分数 $\frac{a}{b}$ で表し、$a$ と $b$ が互いに素であるとします。$bx\equiv a\pmod{998244353}$ かつ $0\le x<998244353$ を満たす整数 $x$ を出力してください。このような整数 $x$ は一意に存在することが証明できます。

入出力例

入力 1

10 5 1 2

出力 1

342025319

入出力例 2

選手用ディレクトリ内の pool/pool2.in と pool/pool2.ans を参照してください。

入出力例 3

選手用ディレクトリ内の pool/pool3.in と pool/pool3.ans を参照してください。

注記

$p$ が素数、$x\in[1,p)$ のとき、$x^{p-1}\equiv 1\pmod p$ です。

小課題