题目描述

称一对数组 $a_{1\sim n}$ 和 $b_{1\sim m}$ 合法，当且仅当满足以下条件：

• 对所有 $i,j$，有 $a_i,b_j\in [0,2^k-1]$；
• $a$ 中元素两两不同，$b$ 中元素两两不同；
• 对于 $1\le i\le \min(n,m)$，有 $a_i\ne b_i$；
• $a$ 中所有数的异或和等于 $b$ 中所有数的异或和。

请计算合法数组对 $(a,b)$ 的数量，并对 $10^9+7$ 取模。

输入格式

每个测试点包含多组数据。

第一行一个正整数 $T$，表示数据组数。

对于每组数据，输入一行三个正整数 $n,m,k$。

输出格式

对于每组数据，输出一行一个非负整数，表示答案。

样例 1 输入

8
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

样例 1 输出

0
0
1
9
1
9
2
36

样例 2

见下发文件。

数据范围与约定

对于全部测试数据，满足：

• $1\le T\le 30$；
• $1\le n,m\le 10^6$；
• $1\le k\le 10^9$。