Коров'ячі класики (Золото)

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

Гра відбувається на решітці розміром r на c (2 ≤ r ≤ 750, 2 ≤ c ≤ 750), де кожна клітинка позначена цілим числом від 1 до k (1 ≤ k ≤ r * c). Корови виконують послідовність стрибків, починаючи з лівого верхнього кута і закінчуючи в правому нижньому куті. Стрибок вважається коректним, якщо виконуються наступні умови:

1. Ви стрибаєте на клітинку з іншим числом.

2. Клітинка, на яку Ви стрибаєте, знаходиться як мінімум на один рядок нижче від поточної клітинки.

3. Клітинка, на яку Ви стрибаєте, знаходиться як мінімум на одну колонку правіше від поточної клітинки.

Будь ласка, допоможіть коровам підрахувати кількість можливих різних послідовностей коректних стрибків з лівого верхнього кута в правий нижній.

Вхідні дані

Перший рядок містить цілі числа r, c, k. Кожен з наступних r рядків містить c цілих чисел, кожне з яких знаходиться в діапазоні від 1 до k.

Вихідні дані

Виведіть кількість різних способів перестрибнути з лівого верхнього кута в правий нижній, за модулем 10^9 + 7.

Приклади