守卫II Guards II

题意翻译

# 【题目描述】 在$n$行$m$列的棋盘里放$k$个车，使得边界的格子都能被攻击到。输出方案总数除以$10^9+7$的余数。 # 【输入格式】 有多组数据。 输入第一行为一个整数$T(T\leq20000)$，表示数据组数。 每组数据占一行，为三个整数$n,m,k(n,m,k\leq100)$ # 【输出格式】 对于第$i$组数据，格式为： ``Case i: answer`` $answer$为方案总数$(mod$ $10^9+7)$

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=4035 [PDF](https://uva.onlinejudge.org/external/125/p12590.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12590/449a706da72848f4696c3f2d6120c780c63c7664.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12590/3865300dbb5bcc77f2cfd0701e315be9330616e8.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12590/c55c7b2aeeab4cdd8dd93f54c4174b9027bb4929.png)

输入输出样例

输入样例 #1

4
10 10 2
5 6 1
2 2 3
2 2 5

输出样例 #1

Case 1: 2
Case 2: 0
Case 3: 4
Case 4: 0