В связи с карантином, у Cайкромофта появилось больше свободного времени для реализации новых функций в «Celex-2021». Разработчики сделали новую функцию GAZ-GIZ, которая от левого верхнего угла бесконечно заполняет бесконечную вправо и вниз таблицу следующим образом:
Клетка с координатами \((x, y)\) находится на пересечение \(x\)-й строки и \(y\)-го столбца. Левая верхняя клетка \((1,1)\) содержит число \(1\).
Разработчики функции SUM тоже не спят. От скуки они сговорились с разработчиками функции RAND, поэтому они добавили возможность посчитать сумму на произвольном пути от одной клетки до другой, передвигаясь вниз или вправо. Формально, из клетки \((x,y)\) за один шаг можно переместиться в клетку \((x+1, y)\) или \((x, y+1)\).
После очередного обновления Dinwows, Левиан решил изучать «Celex-2021» (ведь он хочет стать бухгалтером!). После заполнения таблицы функцией GAZ-GIZ он попросил вас посчитать количество возможных различных сумм на пути от заданной клетки \((x_1, y_1)\) до другой заданной клетки \((x_2, y_2\)), если за один ход вы можете ходить только на одну ячейку вниз или вправо.
Формально, рассмотрим все пути из клетки \((x_1, y_1)\) в клетку \((x_2, y_2)\) такие, что каждая следующая клетка в пути располагается либо справа, либо снизу от предыдущей. Посчитайте количество различных сумм значений элементов для всех таких путей.