UVA11806 Cheerleaders

你有一个 $n\times m$ 的网格图，现在你要将 $k$ 个人放在网格中，满足以下条件： - 网格图的四个边都至少有一个人； - 每个格子上不能有两个人； - 每个人必须都有位置。 求放的方案数，答案对 $10^6+7$ 取模。 注意：四个角的人可以同时算作在两个边上。

第一行一个整数 $T$ 表示数据组数。 对于每组数据：一行三个整数 $n,m,k$，如题意所示。

每组数据一行一个整数。见样例。

数据范围：$T\le 50,2\le n,m\le 20,k\le 500$。