Cow Hopscotch

Farmer John's cows have invented their own version of hopscotch that is played on an R × C grid. Each square of the grid is labeled with an integer from 1 to K. A jump from one square to another is valid if and only if:

1. The destination square's label is different from the current square's label.
2. The destination square is at least one row below the current square.
3. The destination square is at least one column to the right of the current square.

The cows start in the top-left square and want to reach the bottom-right square by a sequence of valid jumps. Given the grid, compute the total number of distinct jump sequences that take them from the top-left to the bottom-right square.

Input Format: The first line contains three integers R, C, and K, where 2 ≤ R, C ≤ 750 and 1 ≤ K ≤ R × C. This is followed by R lines each containing C integers representing the grid.

inputFormat

The input begins with three integers R, C, and K. The following R lines each contain C integers. Each integer is between 1 and K (inclusive) representing the label of a cell in the grid.

outputFormat

Output a single integer: the number of valid sequences of jumps from the top-left square to the bottom-right square.

sample

2 2 4
1 2
3 4

1