SPOJ in Gyumri

   У вас появился шанс поиграть в очень старую игру. Игра ведется на квадратном поле размера NxN. В каждую клетку поля вписано число. Ваша фишка начинает в верхней левой клетке. Вы можете передвигать фишку только вправо или вниз, причем фишку можно передвинуть на новую клетку, только если модуль разности между числами, вписанными на текущей клетке и на новой, не более M. Цель игры – довести фишку до правой нижней клетки. Ваша задача – подсчитать количество различных способов довести фишку из левой верхней клетки в правую нижнюю. Два способа считаются различными, если они отличаются хотя бы одной клеткой.

Входные данные.

   N M

   A[1,1] A[1,2] … A[1, N]

   …

   A[N,1] A[N,2] … A[N,N]

Где: N – размер игрового поля; M – предел разницы между числами на клетках между которыми совершается переход; A[i,j] – описание игрового поля. Все числа целые (1 ≤ N,M,A[i,j] ≤ 20).

Выходные данные.

   Ans - количество различных способов довести фишку из левой верхней клетки в правую нижнюю.

Пример.