Фермер Джон придумал игру для своих коров
Она играется на решётке 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 |