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

Составим таблицу, в которой посчитаем число путей, ведущих в данную ячейку и не содержащих ни одной жилы. Число путей равно сумме числа путей, ведущих в соседнюю ячейку сверху, и числа путей, ведущих в соседнюю ячейку слева, так как только из них можно попасть в текущую ячейку. В ячейки с золотом поставим нули.Проделав вычисления, получаем ответ 106.