Посетители ИТ-кампуса «НЕЙМАРК» не только сильные программисты, но и физически крепкие люди! Кто-то занимается плаванием, кто-то — греблей, а кто-то — скалолазанием!

Мастер Игорь — опора скалолазного движения в регионе. Однажды он пошел в поход в горы, чтобы подняться на вершину одной из них. Как опытный скалолаз, Игорь решил не подниматься в гору по тропинкам, а использовать свои навыки, чтобы подняться в гору строго вертикально.

Игорь нашел прямоугольную вертикальную часть горы и мысленно разбил её на $$$n$$$ горизонтальных уровней. Каждый из уровней Игорь мысленно разбил вертикальными перегородками на $$$m$$$ участков. Осмотрев эти участки, Игорь нашел удобные выступы, за которые можно держаться руками (далее будем называть их зацепки). Итого, найденную часть горы можно представить в виде прямоугольника $$$n \times m$$$, в некоторых клетках которого расположены зацепки.

Как опытный программист, Игорь решил посчитать, сколько существует правильных трасс. Трасса — это последовательность различных участков с зацепками. Трасса считается правильной, если выполняются следующие условия:

• первая зацепка трассы находится на самом нижнем уровне (строка $$$n$$$);
• последняя зацепка трассы находится на самом верхнем уровне (строка $$$1$$$);
• каждая следующая зацепка находится не ниже предыдущей;
• на каждом уровне (то есть на каждой строке прямоугольника) используется хотя бы одна зацепка;
• на каждом уровне используются максимум две зацепки (у Игоря всего две руки);
• Игорь может дотянуться от текущей зацепки до следующей, если расстояние между центрами соответствующих участков не превосходит размаха рук Игоря.

Размах рук Игоря равен $$$d$$$, то есть он может перейти с одной зацепки на другую, если Евклидово расстояние между центрами соответствующих участков не превосходит $$$d$$$. Расстояние между участками ($$$i_1, j_1$$$) и ($$$i_2, j_2$$$) равняется $$$\sqrt{(i_1 - i_2) ^ 2 + (j_1 - j_2) ^ 2}$$$.

Посчитайте, сколько существует различных правильных трасс. Две трассы считаются различными, если они отличаются списком используемых участков или порядком следования этих участков.