久莲是個愛玩的女孩子。

暑假終於到了，久莲決定請她的朋友們來游泳，她打算先在她家的私人海灘外圈一塊長方形的海域作為游泳場。然而大海裡有著各種各樣的危險，有些地方水太深，有些地方有帶毒的水母出沒。她想讓圈出來的這一塊海域都是安全的。

經過初步的分析，她把這塊海域抽象成了一個底邊長為 $N$ 米、高為 $1001$ 米的長方形網格。其中網格的底邊對應著她家的私人海灘，每一個 $1 \times 1$ 的小正方形都代表著一個單位海域。她拜託了她爸爸明天去測量每一個小正方形是否安全。在得知了資訊之後，她要做的就是圈出她想要的游泳場啦。

她心目中理想的游泳場滿足如下三個條件：

• 必須保證安全性。即游泳場中的每一個單位海域都是安全的。
• 必須是矩形。即游泳場必須是整個網格中的一個 $a \times b$ 的子網格。
• 必須和海灘相鄰。即游泳場的下邊界必須緊貼網格的下邊界。

例如：當 $N = 5$ 時，若測量的結果如下（因為 $1001$ 太大，這兒只畫出網格最下面三行的資訊，其他部分都是危險的）。

那麼她可以選取最下面一行的 $1 \times 4$ 的子海域，也可以選擇第三列的 $3 \times 1$ 的子海域。注意她不能選取最上面一行的 $1 \times 5$ 的子海域，因為它沒有與海灘相鄰。

為了讓朋友們玩得開心，她想讓游泳場的面積盡可能大。因此她會選取最下面那一行的 $1 \times 4$ 的子海域作為最終方案。

雖然她要明天才能知道每一個單位海域是否安全，但是她現在就想行動起來估計一下她的游泳場面積有多大。經過簡單的估計，她假設每一個單位海域都有獨立的 $q$ 的機率是安全的，$1 - q$ 的機率是不安全的。她想要知道她能選擇的最大的游泳場的面積恰好為 $K$ 的機率是多少。

然而久莲對數學並不感興趣，因此她想讓你來幫她計算一下這個數值。

輸入格式

從檔案 pool.in 中讀入資料。

輸入一行四個正整數 $N, K, x, y$，其中 $1 \le x < y < 998244353$。$q$ 的取值為 $\frac{x}{y}$。

輸出格式

輸出到檔案 pool.out 中。

輸出一行一個整數表示答案在模 $998244353$ 意義下的取值。

即設答案化為最簡分式後的形式為 $\frac{a}{b}$，其中 $a$ 和 $b$ 互質。輸出整數 $x$ 使得 $bx \equiv a \pmod{998244353}$ 且 $0 \le x < 998244353$。可以證明這樣的整數 $x$ 是唯一的。

範例

輸入格式 1

10 5 1 2

輸出格式 1

342025319

範例 2

見選手目錄下的 pool/pool2.in 與 pool/pool2.ans。

範例 3

見選手目錄下的 pool/pool3.in 與 pool/pool3.ans。

說明

$x^{p-1} \equiv 1 \pmod p$，其中 $p$ 為質數，$x \in [1, p)$。

子任務