Задача . Cow Hopscotch (Silver)

Фермер Джон придумал игру для своих коров

Она играется на решётке R*C (2 <= R <= 100, 2 <= C <= 100), где каждый квадрат помечен целым числом от 1 до K (1 <= K <= R*C). Коровы выполняют последовательность прыжков, начиная в левом верхнем квадрате и заканчивая в правом нижнем квадрате и прыжок является корректным если и только если:

1) Вы прыгаете на квадрат c другим числом

2) Квадрат, куда Вы прыгаете, как минимум на одну строку ниже квадрата, в котором Вы сейчас стоите

3) Квадрат, в который Вы прыгаете как минимум на одну колонку правее квадрата, в котором Вы сейчас стоите

Пожалуйста, помогите коровам вычислить количество возможных различных последовательностей корректных прыжков из левого верхнего квадрата в правый нижний.

Формат входных данных

Первая строка ввода содержит целые числа R, C, K. Каждая из следующих R строк содержит C целых чисел, каждое в интервале 1..K.

Формат выходных данных

Выведите количество различных способов пропрыгать из левого верхнего угла в правый нижний, по модулю 1000000007.

5