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