Farmer John came up with a game for his cows
It is played on an R*C grid (2 <= R <= 750, 2 <= C <= 750), where each square is labeled with an integer from 1 to K (1 <= K <= R* C). Cows perform a sequence of jumps starting at the top left square and ending at the bottom right square, and the jump is legal if and only if:
1) You jump to a square with a different number
2) The square you are jumping to is at least one row below the square you are currently standing in
3) The square you are jumping into is at least one column to the right of the square you are currently standing in
Please help the cows calculate the number of possible different sequences of correct jumps from the upper left square to the lower right one.
INPUT FORMAT:
The first line of input contains the integers R, C, K. Each of the next R lines contains C integers, each in the interval 1..K.
OUTPUT FORMAT:
Print the number of different ways to jump from the upper left corner to the lower right, modulo 1000000007.