在大多数专业的体育赛事中，啦啦队在娱乐观众方面起着重要的作用。他们一般是在比赛前和比赛休息时间进行表演。世界杯也是如此。通常啦啦队组成一个团体，在场地中央表演。除了这一组之外，一些啦啦队员被安排在场地四周，这样的话他们能够更加靠近观众。组织者希望确保在场地的每个边至少有一个啦啦队队员。在这个题目中，我们可以把场地看成是一个M*N的矩形网格，如下图：

安排啦啦队的限制条件如下：
1、广场的四条边（第一行、最后一行、第一列、最后一列），都至少有一个啦啦队员。注意站在广场四个角的啦啦队员可以认为同时占据了一行和一列
2、一个小网格中只能有一个啦啦队员。
3、每个啦啦队员都站在网格中，也就是没有啦啦队员被排除在外。
组织者想知道，满足上述限制条件的情况下，他们可以有多少种方式来安排啦啦队员。

第一行，一个整数T（T≤50）表示测试数据的组数
接下来T行，一行表示一组测试数据，包含三个正整数M,N,K，分别表示网格是M行，N列以及啦啦队员的数量K。2≤M,N≤20，K≤500

对每一组测试数据，输出一行，先输出测试数据的编号，紧接着是一个“:”，然后输出安排啦啦队队员的方式总数，结果可能很大，最终答案输出取模1000007的结果。

容斥 UVA level6