﻿ Ningbo University of Technology Online Judge :: Good Bye 2015 (One University One Question) Round III :: Coloring
• ### [B] Coloring

• 时间限制: 2000 ms　内存限制: 262144 K
• 问题描述
• New year is coming, I came back home, so my niece wants to play with me, she has board which size is n * m (which means it has n * m cells). Now she wants me to draw this board with using no more than k different colors, but she is so naughty that if the manhattan distance between two different cells is an odd number, i can’t draw them with the same color. Finally, i need to tell her the total number of different ways to draw the board. Who can help me? Note that the manhattan distance between (x1, y1) and (x2, y2) is equal to |x1 - x2| + |y1 - y2|. print your answer mod 1e9+7

• 输入
• Input starts with integer T ( 1 <= T <= 10000) denoting the number of test case.
For each test case, n, m, k (1 <= n, m, k <= 25) will be given.
• 输出
• For each test case, print the number of different ways o draw the board mod 1e9+7,without breaking the rules.
• 样例输入
• ```3
3 3 3
2 2 2
10 10 10```
• 样例输出
• ```138
2
728899679```
• 提示
• `无`
• 来源
• `本站或者转载`
• 操作
﻿