問題一覧 > 通常問題

No.1815 K色問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 : okkuukenkenokkuukenken / テスター : 沙耶花沙耶花
0 ProblemId : 3838 / 自分の提出
問題文最終更新日: 2024-03-13 11:38:18
この問題はPythonでACできることが確認されていません。
Python使いの皆様は代わりにPyPyで提出することを推奨します。
追記:PythonでのAC者が出ました。

問題文

$N\times M$ の格子をちょうど $K$ 色で塗り分けます。
$K$ 色全てを使わなければいけません。
隣り合うマスが同じ色になってもいけません。
塗り分け方が何通りかを $10^9+7$ で割った余りを出力してください。

入力

$N\ M\ K$

$1\le N\le3$
$1\le M\le10^{18}$
$1\le K\le2\times10^5$
入力は全て整数

出力

塗り分け方が何通りかを $10^9+7$ で割った余りを $1$ 行で出力してください。
最後に改行を入れてください。

サンプル

サンプル1
入力
3 1 3
出力
6

$3\times1$ の格子をちょうど $3$ 色で塗り分ける方法は $6$ 通りです。

サンプル2
入力
2 2 10
出力
0

$2\times2$ の格子で $10$ 色を使い切ることはできません。

サンプル3
入力
3 50 4
出力
70331496

塗り分け方が何通りかを $10^9+7$ で割った余りを出力してください。

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