提示: 欢迎访问OurACM平台。
Problem 2174 卷福的难题

Accept: 9    Submit: 39
Time Limit: 5000 mSec    Memory Limit : 32768 KB

Problem Description

这天,无聊的卷福没有有趣的案子可玩,于是他给花生出了一道题!

卷福拿了一些硬币排成n*m的矩阵,最初所有硬币都是正面朝上。花生每次操作可以选择一个子矩阵,将其中的硬币全部翻转。卷福只允许花生操作至多k次,他想让花生告诉他最后能得到多少不同的矩阵。

花生躲在屋里尝试了一个星期了,还是没有数完。快来帮他解决这个问题!

Input

输入第一行包含一个整数t(t<=100),表示输入组数。

每组数据占一行为三个整数n, m, k(1<=n<=500, 1<=m<=2, 0<=k<=250),表示矩阵大小和允许操作的最多次数。

Output

输出一个整数占一行,为不同的矩阵的个数。由于答案比较大,请将答案mod 1000000007。

Sample Input

2 3 1 1 3 2 2

Sample Output

7 64

Submit  Back  Status  Discuss