#892 Cats & Soup: Magic Recipe

問題文

問題文の言語

以下の問題文は、ゲーム「猫とスープ：魔法のレシピ」を簡略化したものです。

アイテムには星と月の二種類があり、それぞれレベル $1$ から $M$ まである。インベントリには $N$ 個の枠があり、最初はすべて空である。各アイテムは一枠を使う。

次の操作を何度でも行える。

空き枠があれば、レベル $1$ のアイテムを一つ生成する。星が生成される確率は $a/b$ 、月が生成される確率は $1-a/b$ である。生成される種類は毎回独立である。
同じ種類かつ同じレベル $x$ のアイテムを二つ選んで取り除き、同じ種類のレベル $x+1$ のアイテムを一つ作る。この操作はの場合に限り行え、空き枠は必要ない。

アイテムを捨てたり、これら以外の方法で変更したりすることはできない。各操作は、現在のインベントリとそれまでの生成結果を見て選んでよい。

レベル $L$ の星を一度でも作ることが目標である。すべての戦略の中で、目標を達成する確率の最大値を求めよ。その確率を既約分数 $p/q$ と表したとき、 $p\times q^{-1}\bmod998\,244\,353$ を出力せよ。は法におけるの乗法逆元である。

入力は次の形式で与えられる。

$N\ M\ L$ $a\ b$

求めた値を $0$ 以上 $998\,244\,353$ 未満の整数として出力せよ。

#	得点	制約
1	20	$N\leq3$ , $M\leq3$ .
2	20	$L=1$ .

例 1

入力例

2 2 2
1 2

出力例

748683265

最初の二回がどちらも星の場合だけ目標を達成できる。確率は $1/4$ で、法 $998\,244\,353$ では $748\,683\,265$ と表される。

例 2

入力例

3 3 1
1 2

出力例

7798785

一度でも星を生成すれば成功する。可能な合成をすべて行うと、最初の七回がすべて月の場合だけ失敗するため、最大確率は $127 /$ である。