問題一覧 > 通常問題

No.1759 Silver Tour

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 11
作問者 : NyaanNyaanNyaanNyaan / テスター : PCTprobabilityPCTprobability tokusakuraitokusakurai
1 ProblemId : 7323 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-20 14:00:55

問題文

縦横 $H \times W$ の将棋盤と銀将の駒 $1$ 枚があります。

銀将は図 $1$ のように前 $3$ マスと斜め後ろに動かすことができます。ただし、動かした先が盤の内部である必要があります。

より厳密には、上から $i$ 行目で左から $j$ 列目のマスを $(i,j)$ と表したとき、 $(i,j)$ に置かれている銀は $(i-1,j-1),(i-1,j),(i-1,j+1),(i+1,j-1),(i+1,j+1)$ に動かすことができます。

次の条件を満たすように銀将を動かすことを「銀の全マス巡り」と呼びます。

  • 盤上の最下段、すなわち $(H,j)$ $(1 \leq j \leq W)$ のいずれかに銀を置き、銀が同じマスを複数回通ることなく全てのマスを通るように銀を動かす。

例えば図 $2$ に示す動かし方は $H = W = 2$ のときの銀の全マス巡りの一例です。

銀の全マス巡りとしてあり得るものの種類数を $M$ で割ったあまりを求めてください。
ただし、銀の全マス巡りが異なるとは、動かし方をマス目の列として見たときに異なることを言います。

制約

  • 入力は全て整数である。
  • $1 \leq H \leq 50$
  • $1 \leq W \leq 50$
  • $9 \times 10^8 \leq M \leq 10^9$

入力

$H\ W\ M$

出力

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

サンプル

サンプル1
入力
2 2 998244353
出力
2

条件を満たす銀の全マス巡りは、 図 $2$ で挙げたものと、それを左右反転させたものの合計 $2$ 通りです。

サンプル2
入力
9 9 998244353
出力
0

$9 \times 9$ の将棋盤では銀の全マス巡りができないので、条件を満たす動かし方は存在しません。

サンプル3
入力
6 5 924844033
出力
60

サンプル3
入力
50 50 1000000000
出力
999575486

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。