Фермер Джон придумал игру для своих коров
Она играется на решётке R*C (2 <= R <= 750, 2 <= C <= 750), где
каждый квадрат помечен целым числом от 1 до K (1 <= K <= R*C). Коровы выполняют
последовательность прыжков, начиная в левом верхнем квадрате и заканчивая в правом нижнем квадрате и прыжок является корректным если и только если:
1) Вы прыгаете на квадрат c другим числом
2) Квадрат, куда Вы прыгаете, как минимум на одну строку ниже квадрата, в котором Вы
сейчас стоите
3) Квадрат, в который Вы прыгаете как минимум на одну колонку правее квадрата, в котором
Вы сейчас стоите
Пожалуйста, помогите коровам вычислить количество возможных различных последовательностей
корректных прыжков из левого верхнего квадрата в правый нижний.
Формат входных данных
Первая строка ввода содержит целые числа R, C, K.
Каждая из следующих R строк содержит C целых чисел, каждое в интервале 1..K.
Формат выходных данных
Выведите количество различных способов пропрыгать из левого верхнего угла в правый нижний,
по модулю 1000000007.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4 4
1 1 1 1
1 3 2 1
1 2 4 1
1 1 1 1
|
5
|