Problem Description

题目描述

给定 $n$，$m$，$k$。

问有多少个 $n$ 行 $m$ 列的 $01$ 矩阵 $a$ 满足：

对于任意大小为 $k$ 的连通块（四连通），其内所有数异或和为 $0$。

答案对 $10^9+7$ 取模。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

一行三个正整数 $n$，$m$，$k$。

输出格式

对于每组数据：输出一行一个整数，表示这组数据的答案对 $10^9+7$ 取模的结果。

样例

样例 1

提示

本题采用捆绑测试。

对于所有测试数据，保证：

$T\le50$，$1\le n,m,k\le10^9$。

3
1 8 6
5 5 5
114 514 1919810

32
1
195408007