Игровое поле N x M заполняется целыми числами, одно
неотрицательное целое число в каждой клетке. Цель игры состоит в том,
чтобы пройти по любому разрешенному пути от верхнего левого угла до правого
нижнего. Целое число в каждой клетке указывает, какой длины шаг должен быть из
текущей клетки. Все шаги могут быть или направо или вниз. Если в результате
какого-либо шага игрок покидает пределы поля, такой шаг запрещается.
Требуется написать программу, которая определит число различных
вариантов путей от верхнего левого угла до правого нижнего.
На рисунке приведен пример игрового поля 3 x 4, для которого существует
три возможных варианта путей.
Формат входных данных:
Входной файл
содержит в первой строке размеры поля N (1 ≤ N ≤ 70)
и M (1 ≤ M ≤ 70). В последующих N строках
входного файла, каждая из которых описывает отдельную строку игрового поля,
записаны через пробел по M целых чисел – длины шагов из клеток данной
строки.
Формат выходных данных:
Выходной файл
должен содержать одно число - число различных вариантов путей от верхнего
левого угла до правого нижнего. Для каждого поля будет менее чем 231
различных путей.
Пример файлов входных и выходных данных:
|
STDIN
|
STDOUT
|
|
3 4
2 1 1 2
3 2 1 44
3 1 1 0
|
3
|
