{"trustable":false,"sections":[{"title":"背景","value":{"format":"MD","content":"在大多数职业体育赛事中,啦啦队在娱乐观众方面发挥着重要作用。在休息时间和比赛开始前,他们的作用很大。世界杯足球赛也不例外。 拉拉队通常组成一个团体,在场地中央表演。除了这一组,她们中的一些人还被安排在边线外,以便离观众更近。组织者希望确保四条边线上至少各有一名啦啦队员。对于这个问题,我们将比赛场地建模为一个 M × N 的矩形网格。放置啦啦队长的限制条件如下:\n\n- 四条边上至少各有一名啦啦队长。注意,将啦啦队员放在角落单元格中会同时覆盖两个边。\n\n- 一个网格里最多只能有一名拉拉队员。\n- 所有可用的啦啦队员都必须被分配到一个单元。也就是说,一个都不能少。\n\n(图略)\n\n组织者想知道,在保持上述限制的前提下,他们可以用多少种方法来放置啦啦队员。如果至少有一个单元格中包含一名拉拉队队员,而另一个单元格中没有,那么这两个位置就是不同的"}},{"title":"输入","value":{"format":"MD","content":"第一行输入包含一个正整数 T ≤ 50,表示测试用例的数量。随后的 T 行分别描述一个测试用例。每个案例由三个非负整数组成:2 ≤ M、N ≤ 20 和 K ≤ 500。这里,M 是网格的行数,N 是网格的列数。K 表示必须分配给网格单元格的啦啦队人数。"}},{"title":"输出","value":{"format":"MD","content":"每输入一例,就会有一行输出。它首先包含个案编号,然后是前面描述的拉拉队长放置方式的数量。具体格式请查看输出示例。请注意,数字可以任意大。因此,您必须输出模数为 1000007 的答案。"}},{"title":"样例","value":{"format":"MD","content":"##### Sample Input\n\n```\n2\n2 2 1\n2 3 2\n```\n\n##### Sample Output\n\n```\nCase 1: 0\nCase 2: 2\n```\n\n"}}]}