该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

座位安排

题目描述

育华学校的一间教室里有 $n$ 排座位，每排有 $m$ 个座位。现在要安排 $k$ 位同学入座，要求任意两位同学不能坐在同一排，也不能坐在同一列。请问有多少种不同的座位安排方式？

输入格式

输入包含一行，三个正整数 $n$、$m$ 和 $k$（$1\leq k\leq\min(n,m)$，$1\leq n\leq 10$，$1\leq m\leq 10$），分别表示座位的排数、每排的座位数以及需要安排入座的同学数量。

输出格式

输出一个整数，表示不同的座位安排方式的数量。

样例

输入样例

3 3 2

输出样例

18

解释

先从 3 排中选 2 排，有 $C_{3}^2=\frac{3!}{2!(3 - 2)!}=3$ 种选法。 对于选出的 2 排，第一排有 3 个座位可选，第二排不能与第一排的列相同，所以有 2 个座位可选。 根据排列组合的乘法原理，总的安排方式有 $A_{3}^2\times C_{3}^2=3\times2\times3 = 18$ 种。

数据范围

• 对于 30% 的数据，$1\leq k\leq\min(n,m)$，$1\leq n\leq 5$，$1\leq m\leq 5$。
• 对于 60% 的数据，$1\leq k\leq\min(n,m)$，$1\leq n\leq 8$，$1\leq m\leq 8$。
• 对于 100% 的数据，$1\leq k\leq\min(n,m)$，$1\leq n\leq 10$，$1\leq m\leq 10$。