Aly being one of the smartest guys in his third grade class solved the question "How many ways to assign K cells for rooks in an N*M such that no two rooks are attacking each other" (A rook is a chess piece that can attack other pieces on the same row or the same column) but he was only able to solve it when N*M didn't exceed 10. After some days one of his classmates said he was able to solve it even if N*M reached 100. Aly kept asking how he did it and after questioning a lot of people he knew that he used a program to calculate this for him so he decided to challenge him in front of all his classmates but to do that he also needed a program that not only solve the problem when N*M reaches 100 but when N and M each reach 1,000,000 and he came for you to do that program for him but as he knows that the answer can be really big he wanted the program to output the number of ways modulo 1,000,000,007.

Input

The first and only line of input contains three numbers N, M and K( 1 <= N,M <= 1,000,000 , 1 <= K <= N*M ).

Output

The number of ways required modulo 1,000,000,007.

Example

Input:
4 4 4

Output:
24