весна 12: Тур 02.04.12

Правительство Байтландии объявило 2012 год Годом здоровья. В честь этого в национальном столичном парке было решено построить беговую дорожку для проведения ежегодной семейной эстафеты. Национальный парк представляет собой прямоугольник размером N на M метров, разделенный на квадраты одинакового размера площадью один м^2. Другими словами, парку соответствует прямоугольная таблица с N строками и M столбцами. Строки нумеруются сверху вниз начиная с единицы, столбцы нумеруются слева направо начиная с единицы. Следовательно, каждому квадрату можно поставить в соответствие пару чисел (X, Y), где X – это номер строки, а Y – номер столбца, на пересечении которых он находится.
Первоначально беговую дорожку предполагалось сделать в виде прямоугольника. Однако по мнению экологов Министерства природных ресурсов Байтландии, ее следует сделать крестообразной формы, в соответствии с мировыми стандартами.
Беговая дорожка крестообразной формы конструируется следующим образом:
1. выбирается горизонтальная полоса шириной один квадрат и длиной H квадратов;
2. выбирается вертикальная полоса шириной один квадрат и длиной V квадратов, пересекающаяся с горизонтальной полосой, где H и V – любые натуральные числа (квадрат, принадлежащий одновременно горизонтальной и вертикальной полосам, называется базовым);
3. по всей длине каждой из полос посередине устанавливаются ограждения длиной H - 1 и V - 1 метров соответственно.
Эстафета начинается и заканчивается в базовом квадрате. Забег осуществляется вдоль ограждения беговой дорожки, как это показано на рисунке.

Квадраты парка могут быть двух типов: содержащие дерево либо не содержащие дерево (пустой квадрат). Будем считать, что если квадрат содержит дерево, то оно занимает всю его площадь. Стоимость постройки беговой дорожки зависит не только от количества квадратов, но и от их типа. Известно, что стоимость оборудования пустого квадрата для беговой дорожки составляет один байт (байт – национальная валюта Байтландии), а оборудование квадрата, содержащего дерево, составляет два байта, так как дерево требует предварительного сноса. На создание беговой дорожки правительство Байтландии выделило S байт. Ваша задача – определить количество различных способов постройки беговой дорожки крестообразной формы. Два способа постройки беговой дорожки считаются различными, если различны множества соответствующих им квадратов либо различны базовые квадраты.

3 4 3
.#..
....
..#.

70

5 7 6
#...#..
.....#.
#......
.......
.#....#

1395