0643 - Underground labyrinth(地下迷宮)

課題

platypusは迷宮探索が大好きです。今日も各地の迷宮の攻略を頑張っています。
platypusは自宅の地下室が広いので、そこに迷宮の一室を練習用に作ることにしました。
部屋は東西にWメートル、南北にHメートルです。
この部屋にplatypusは迫りくる石柱の罠を仕掛けました。
石柱の罠は、東側の壁および南側の壁に1メートル間隔で設置されています。
platypusは別室のモニターから、罠の制御をすることができます。
モニターには最初、以下のようにボタンが右側にH個、下側にW個ならんでいます。

□□□□□○
□□□□□○
□□□□□○
○○○○○

右側のボタンを押すと、
部屋の東側の壁から石柱が飛んできます。
例えば、下の図に示されているボタンを押したとき、

□□□□□○
□□□□□●
□□□□□○
○○○○○

東側から石柱が飛び出し、部屋を２つに分断します。

□□□□□○
■■■■■●
□□□□□○
○○○○○

また、下側のボタンを押すと、
部屋の南側の壁から石柱が飛んできます。
例えば、下の図に示されているボタンを押したとき、

□□□□□○
■■■■■○
□□□□□○
○○○●○

南側から石柱が飛び出し、部屋の下のスペースをさらに２つに分断します。
この時、石柱は途中に別の石柱がある場合そこで止まることに注意してください。

□□□□□○
■■■■■●
□□□■□○
○○○●○

なお、石柱が動かせない場合、ボタンも押せないことに注意してください。
platypusはいずれいくつかのボタンを押していけば必ず部屋を石柱で埋め尽くせることに気づきました。
埋めつくすボタンの押し方の順番の通り数を自然数Mで割った余りを出力しなさい。

入力

H W M

1 行に整数 H W M が与えられる。

出力

通り数を M で割った余りを出力せよ。出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下の制約を満たす。

• 1 ≦ H, W ≦ 200
• 1 ≦ M ≦ 10⁹+7

20点分のテストケースは以下の条件を満たす。

• 1 ≦ H, W ≦ 50

---

入出力例

入力例1

2 3 997

出力例1

35

解説

右側のボタンを上からA,B
下側のボタンを右から1,2,3とすると、

□□□A
□□□B
３２１

以下の35通りのボタンの押し方が存在します。
32AB 32BA 23AB 23BA
2A3B 2B3A 2AB3 2BA3
3A21 3A12 32A1 23A1
2A31 2A13 3A2B A123
A132 A213 A231 A312
A321 A32B A23B A2B3
123 132 213 231 312
321 3AB 3BA A3B AB BA
この時、B1Aのように、石柱を動かせないようなボタンの押し方は
カウントしないことに注意しなさい。

入力例2

7 7 114514

出力例2

68064

ボタンの押し方は6749981280通りあるため、
114514で割った余りの68064を出力します。

入力例3

198 189 1000000007

出力例3

804294882

入力例3は一部の部分点の制約を満たさないことに注意せよ。