Cow Hopscotch

Time limit1sMemory limit256 MB

Summary

Count paths from the top-left to the bottom-right cell moving down and right where consecutive cells hold different values.

Level: Medium7 of 10
Topics: Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

Farmer John's cows copied the human game of hopscotch and invented a version of their own. Animals that weigh close to a ton play it, so a round usually ends in a mess, and the cows still gather for it almost every afternoon.

The board is an $R \times C$ grid, and every square holds one integer between $1$ and $K$ .

A cow starts on the top left square and reaches the bottom right square with a sequence of jumps. A jump from the current square to another square is allowed when all three conditions hold.

The square you jump to holds an integer different from the integer on the current square.
The square you jump to is at least one row below the current square.
The square you jump to is at least one column to the right of the current square.

Count the different sequences of valid jumps that take a cow from the top left square to the bottom right square. Two sequences count as different when the lists of visited squares differ.

Input

The first line contains $R$ , $C$ , and $K$ . ( $2 \le R \le 750$ , $2 \le C \le 750$ , $1 \le K \le R \times C$ )

Each of the next $R$ lines contains $C$ integers, all between $1$ and $K$ .

Output

Print the number of ways to get from the top left square to the bottom right square, modulo $1000000007$ .

Examples7

Example 1

Input

Expected output

Example 2
Input
```
2 2 2
1 2
2 1
```
Expected output
```
0
```
Example 3
Input
```
2 2 2
1 1
1 2
```
Expected output
```
1
```
Example 4
Input
```
2 2 1
1 1
1 1
```
Expected output
```
0
```
Example 5
Input
```
3 3 9
1 2 3
4 5 6
7 8 9
```
Expected output
```
2
```

Example 6

Input

5 5 25
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Expected output

Example 7

Input

4 6 3
1 2 3 1 2 3
3 1 2 3 1 2
2 3 1 2 3 1
1 1 2 2 3 3

Expected output