题目描述

在 byteland 的手艺工人 byteman 会制作一种称为 DXBALL 的网状小球，这种小球形如鸟笼，由 $N$ 个等分的纬线与 $M$ 个等分的经线组成，如下图所示：

输入格式

输入文件包含两个整数 $N,M,K$，$N,M$ 表示 DXBALL 的规模，$K$ 表示可以染的颜色数。

输出格式

为了避免高精度运算，输出一个整数，表示方案数 $\bmod 8999999$。 【约定】  0 ≤ n ≤ 100  0 ≤ m ≤ 100  2 ≤ k ≤ 100

1 2 2

24

提示

24种本质不同的方案如下图所示： 旋转，翻折后相同的算一种

题目来源

没有写明来源