给定一个大小为 $x \times y$ 的棋盘和 $k$ 个相同的国王，要求将所有国王放置在棋盘上，使得没有任何两个国王可以互相攻击。如果两个国王在水平、垂直或对角线上相邻，则它们可以互相攻击。
编写一个程序，计算在给定的棋盘上放置 $k$ 个国王的所有可能方案数。由于方案数可能很大，请将结果对 $1,000,000,007$ 取模。
输入格式
输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来的 $T$ 行，每行包含三个整数 $x, y$ 和 $k$，中间用空格隔开。
输出格式
对于每个测试用例，输出方案数对 $1,000,000,007$ 取模的结果。
数据范围
- $0 < T \le 50$
- $2 \le x, y \le 15$
- $1 \le k \le x \cdot y$
样例
输入 1
4 8 8 1 7 7 16 7 7 7 3 7 15
输出 1
64 1 2484382 0