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