問題文

高橋君は、以下の条件を満たすように無限に広がるグリッドを塗りつぶそうと考えています。

• $H\times W$ のグリッドのパターンの繰り返しで塗りつぶす

• ちょうど $K$ 色を使う

このような塗り方は何通りありますか。ただし、回転や裏返しは区別しますが、あるパターンを任意の自然数回右もしくは下に平行移動したものは $1$ 通りと数えます。また色は区別できるものとします。

緑緑青　と　緑青緑　と　青緑緑

は同じパターンです。（右に自然数回移動しています。）

移動により上下左右の範囲外にでたマスは反対側の端に移動します。

赤青緑　　　赤緑赤
緑青青　と　青緑赤
赤赤緑　　　青青緑

は同じパターンです。（右に2回、下に1回平行移動しています。)

入力

$H\ W\ K$

• $1 \le H \times W \le 10$
• $1 \le K \le 3$

出力

答えを $1$ 行に出力して下さい。 最後に改行してください。

サンプル

2 3 2

12

■□□　■■□　■□□　■□□
□□□　□□□　■□□　□■□

■■□　■□■　■■■　■□■
■□□　■□□　□□□　□■□

□□■　□■■　□■■　□■■
■■■　□■■　■□■　■■■

1 1 1

1

3 3 3

2022