Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Cow Hopscotch

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

Ввод Вывод
4 4 4
1 1 1 1
1 3 2 1
1 2 4 1
1 1 1 1
5


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: