中学生网格题

题目描述

n*m的网格,每个格子可以填1~k\ 定义两行是相似的,当将各行中的数升序排序后,完全一致\ 问使得各行两两不相似的方案数\ 对$10^9+7$取模

输入输出格式

输入格式


一行,表示$n,m,k$

输出格式


一行,表示方案数

输入输出样例

输入样例 #1

5 5 5

输出样例 #1

87562025

输入样例 #2

5 5 2

输出样例 #2

780000

输入样例 #3

2 2 2

输出样例 #3

10

说明

$1\le n,m,k \le 50$