문제

충남대학교 알고리즘 동아리 부원인 민재는 $R \times C$ 크기의 격자판 위에서 점프 게임을 하려고 한다. ($2 \le R \le 100, 2 \le C \le 100$) 격자의 각 칸에는 $1$ 이상 $K$ 이하의 정수가 하나씩 적혀 있다. ($1 \le K \le R \times C$)

민재는 맨 왼쪽 위 칸에서 시작하여 맨 오른쪽 아래 칸까지 여러 번의 점프를 통해 이동하려 한다. 점프는 다음 세 조건을 모두 만족할 때만 유효하다:

1. 점프하려는 칸에 적힌 숫자가 현재 칸에 적힌 숫자와 달라야 한다.
2. 점프하려는 칸이 현재 칸보다 적어도 한 줄 아래에 있어야 한다.
3. 점프하려는 칸이 현재 칸보다 적어도 한 칸 오른쪽에 있어야 한다.

민재가 맨 왼쪽 위 칸에서 맨 오른쪽 아래 칸까지 이동할 수 있는 서로 다른 유효한 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $R, C, K$가 공백으로 구분되어 주어진다.

다음 $R$개의 줄에는 격자의 각 칸에 적힌 $C$개의 정수가 공백으로 구분되어 주어진다. 각 정수는 $1$ 이상 $K$ 이하이다.

출력

맨 왼쪽 위 칸에서 맨 오른쪽 아래 칸까지 이동하는 서로 다른 경로의 개수를 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

예제 입력 1

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

예제 출력 1

5