题目描述

电影厅的每列有M个座位，有N列座位。因此座椅形成M x N网格,公司为每个影厅都出售K张票 座位有以下规则：座位被占用时，座位正前方和座位后方的座位以及当前座位左边和右边必须是空的 我们规定如果这一场电影的某个座位是占用的，而另一场的座位是空的，则这两场电影的影厅座位安排是不同的 给你三个数字M，N和K 现在需要从这些座位中选出k个合法的座位。

输入格式

输入的第一行包含一个整数T，表示指定测试用例的数量 每个测试用例由包含三个整数M，N和K的一行组成

T

N*M

输出格式

对于每个测试用例输出一行，由于这个数字可能非常大，我们只求它对420047取模的结果

输出一个数字表示答案对420047取模的结果

3
2 3 2
2 4 4
2 5 1

8
2
10