Октаэдр и Домино
Андрей недавно сделал прорыв в создании головоломок: он изобрел новую головоломку, которая проста для понимания и не похожа на все, что было придумано ранее. Его новая головоломка представляет собой октаэдр, каждая (треугольная) грань которого разделена на n^2 меньших треугольников с помощью 3(n-1) линий, n-1 параллельных каждой стороне грани. Некоторые из этих маленьких треугольников черные, а некоторые белые. Задача состоит в том, чтобы покрыть все белые треугольники треугольными домино, не перекрываясь, оставив черные треугольники непокрытыми. Треугольное домино — это два маленьких треугольника, имеющие общую сторону. Обратите внимание, что домино может покрывать один маленький треугольник на одной стороне октаэдра и другой на соседней стороне (то есть домино можно согнуть посередине). Каждое домино должно покрывать ровно два белых маленьких треугольника (это значит, что нельзя покрыть часть треугольника одним домино, а остальное другим). Сколько решений существует для данной головоломки?
Входные данные
Первая строка входного файла содержит целое число n (1 ≤ n ≤ 4). Следующие 2n строк описывают, какие маленькие треугольники черные, а какие белые. Представьте, что октаэдр стоит на своей вершине, с одной из других вершин, направленной на нас. Тогда маленькие треугольники можно разделить на горизонтальные слои. Самый верхний слой содержит 4 треугольника, по одному на каждую сторону, заканчивающуюся в верхней вершине. Следующий слой содержит 12 треугольников, по 3 на каждую сторону, заканчивающуюся в верхней вершине, и так далее. Размер каждого слоя увеличивается на 8, пока не достигнет 8n-4 в середине, затем следующий слой снова состоит из 8n-4 маленьких треугольников (здесь мы перешли от верхних 4 граней к нижним 4 граням), а затем размер каждого следующего слоя уменьшается на 8, пока мы не достигнем самого нижнего слоя, который содержит всего 4 треугольника. Октаэдр дан слой за слоем, и каждый слой начинается с самого левого маленького треугольника на видимой части октаэдра (четыре "передние" грани), идет слева направо вдоль видимой части, а затем переключается на невидимую часть и идет обратно справа налево. Один слой выделен на изображении выше. Каждый маленький треугольник обозначается либо '.', обозначающим белый треугольник, либо '*', обозначающим черный треугольник.
Выходные данные
Выведите одно целое число — количество возможных покрытий белых треугольников данного октаэдра треугольными домино.