Colorful Domino Tiling

$N$ 行 $M$ 列の格子と、$K$ 種類の色のドミノがある。各色のドミノは無限に使える。一つのドミノは辺を共有する二つのマスを覆い、横向きにも縦向きにも置ける。

ドミノが格子の外にはみ出したり重なったりしないように、すべてのマスを覆う。異なる二つのドミノに覆われたマスのうち一組でも上下左右に隣接する場合、その二つのドミノの色は異ならなければならない。頂点だけで接する場合の制約はない。

ドミノの配置と各ドミノの色を決める方法の数を $998\,244\,353$ で割った余りを求めよ。$K$ 色すべてを使う必要はない。配置が異なる場合、または同じ位置にあるドミノの色が一つでも異なる場合は別の方法とする。回転や反転で一致する場合も、元の格子上の配置や色が異なれば別々に数える。同じ色のドミノ同士は区別しない。

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

$N\ M\ K$

条件を満たす方法の数を $998\,244\,353$ で割った余りを出力せよ。方法が存在しない場合は $\tt{0}$ を出力せよ。

• $1\leq N,M\leq8$.
• $4\leq K\leq100$.
• 入力はすべて整数である。