UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2193. 小球

Statistics 下载数据

Description

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

Input

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

Output

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

Sample Input

1 2 2

Sample Output

24


Hint

24种本质不同的方案如下图所示:



旋转,翻折后相同的算一种

Source