Фермер Джон придумал игру для своих коров
Она играется на решётке r * c (2 ≤ r ≤ 750, 2 ≤ c ≤ 750), где каждый квадрат помечен целым числом от 1 до k (1 ≤ k ≤ r * c). Коровы выполняют последовательность прыжков, начиная в левом верхнем квадрате и заканчивая в правом нижнем квадрате и прыжок является корректным если и только если:
Вы прыгаете на квадрат c другим числом
Квадрат, куда Вы прыгаете, как минимум на одну строку ниже квадрата, в котором Вы сейчас стоите
Квадрат, в который Вы прыгаете как минимум на одну колонку правее квадрата, в котором Вы сейчас стоите
Пожалуйста, помогите коровам вычислить количество возможных различных последовательностей корректных прыжков из левого верхнего квадрата в правый нижний.
Первая строка содержит целые числа r, c, k. Каждая из следующих r строк содержит c целых чисел, каждое в интервале 1..k.
Выведите количество различных способов пропрыгать из левого верхнего угла в правый нижний, по модулю 10^9
+ 7.