#P16128. [2026年山东集训一轮]第三题

[2026年山东集训一轮]第三题

题目描述

称一对数组 a1∼na_{1\sim n} 和 b1∼mb_{1\sim m} 合法,当且仅当满足以下条件:

  • 对所有 i,ji,j,有 ai,bj∈[0,2k−1]a_i,b_j\in [0,2^k-1];
  • aa 中元素两两不同,bb 中元素两两不同;
  • 对于 1≤i≤min⁡(n,m)1\le i\le \min(n,m),有 ai≠bia_i\ne b_i;
  • aa 中所有数的异或和等于 bb 中所有数的异或和。

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

输入格式

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

第一行一个正整数 TT,表示数据组数。

对于每组数据,输入一行三个正整数 n,m,kn,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≤T≤301\le T\le 30;
  • 1≤n,m≤1061\le n,m\le 10^6;
  • 1≤k≤1091\le k\le 10^9。
测试点编号 T≤T\le n≤n\le m≤m\le k≤k\le 其它条件
1∼21\sim 2 4 3 4 无
3∼43\sim 4 30 5
5∼65\sim 6 100 1 8
7∼97\sim 9 10610^6 10910^9
10 2
11∼1311\sim 13 7
14∼1514\sim 15 1000 n=m+1n=m+1
16∼1716\sim 17 3 10610^6
18 30
19∼2019\sim 20 1000 无
21∼2321\sim 23 3 10610^6
24∼2524\sim 25 30