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

После этого Билл решил поиграть с покрытой доской и выложить фотографии в социальных сетях. Сперва он убирает с доски одну из доминошек, тем самым освобождая две клетки. После этого он двигает некоторые доминошки. Доминошку можно двигать только параллельно её длинной стороне. Двигать доминошку в каком-либо направлении можно лишь, если ближайшая клетка в этом направлении сейчас свободна. Билл не хочет забыть исходное расположение доминошек, поэтому он двигает доминошки только так, чтобы каждая доминошка всегда покрывала хотя бы одну клетку, общую с её исходным положением.

После удаления доминошки и нескольких сдвигов (возможно, ни одного), Билл фотографирует получившуюся доску. Однако, Билл использует очень много фильтров, поэтому границы доминошек разглядеть нельзя, и можно увидеть лишь то, какие две клетки на доске свободны. Когда Билл выкладывает фотографию, он возвращает доску в исходное положение и начинает заново.

Билл хочет выложить как можно больше фотографий, но он не будет выкладывать одну и ту же фотографию дважды. Сколько различных фотографий он сможет сделать? Напомним, что фотографии различны, если различны пары свободных клеток на них.