注意

この問題の実行時間制限、メモリ制限はそれぞれ $3340~\text{ms},~128~\text{MB}$ であることに注意してください。また、Writer解のPyPy3での実装の実行時間は $2546~\text{ms}$ です。

元ネタ

ABC334-E Christmas Color Grid 1

ABC334-G Christmas Color Grid 2

問題文

縦 $H$ マス、横 $W$ マスのアドベントカレンダーがあります。このアドベントカレンダーの上から $i$ 行目、左から $j$ 行目のマスをマス $(i,j)$ と表記します。初期状態ではどのマスにも色は塗られていません。

はじめ、はるく君のうれしさは $0$ です。はるく君は、以下の一連の操作を $HW$ 回行います。

• アドベントカレンダーのまだ色が塗られていないマスを無作為に選ぶ。確率 $\dfrac{1}{2}$ でそのマスを緑に塗り、確率 $\dfrac{1}{2}$ でそのマスを赤に塗る。
• この後の操作を完遂したときの緑の連結成分の大きさの $K$ 乗和の期待値を$X$ とし、アドベントカレンダーのまだ色が塗られていないマスの数を $Y$ とする。$\dfrac{X}{Y+1}$ をはるく君のうれしさに加算する。

ここで、アドベントカレンダーにおいて、緑色に塗られたマスを頂点集合、隣り合った $2$ つの緑色のマスを結ぶ辺全体を辺集合とした無向グラフにおける連結成分の大きさの $K$ 乗和を緑の連結成分の大きさの $K$ 乗和と呼びます。ただし、$2$ つのマス $(x,y)$ と $(x^′,y^′)$ が隣り合っているとは、$|x−x^′|+|y−y^′|=1$ であることを指します。

最終的なはるく君のうれしさの期待値を $\bmod~M$ で出力してください。

制約

• $1\leq H,W$
• $HW\leq 25$
• $0\leq K\leq 10^{18}$
• $10^8\leq M\leq 10^9+7$
• $M$ は素数
• 入力はすべて整数

入力

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

$H$ $W$ $K$ $M$

出力

答えを出力せよ。

サンプル

1 1 0 998244353

499122177

3 1 1 998244353

249561091

5 5 1000000000000000000 1000000007

530357272