Разбор добавил Александр Чистяков

Первое утверждение, помогающее анализировать подход к решению данной задачи: каждый нарисованный цикл однозначно определяет некоторую полиминошку (4-связную фигурку из клеточек) не содержащую дырок.
Например:
..**..
.**..*
******
*.**..

Таким образом, очевидное решение на 40 баллов:
перебрать все возможные черно-белые раскраски прямоугольника (всего 2^(M*N) вариантов) и для каждой за O(M*N) проверить: является ли данная фигура требуемой полиминошкой.

Рассмотрим теперь полное решение данной задачи:
Маленькие ограничения на ширину прямоугольника (M<9) посдказывают идею применения профильной динамики вдоль стороны длины N.

При разрезании некоторой полиоминошки на горизонтальные полоски высоты 1 мы получим полоски, состоящие из групп '.' (пустых клеток) и '*' (закрашенных клеток). Будем закрашивать одинаковым цветом группы, которые соединяются сверху от полоски, и разными цветами, которые пока что не соединены между собой.
Набором профилей в данном решении будет множество всех возможных минимальных лексикографически раскрасок таких полосок:
Для M = 6:
-1-1-2
--111-
1-22-1
------
1-2-33
Являются профилями, а
-1112-
-2-1-2
-2-2-1
не являются.

Например, рассмотрим следующее преобразование полиоминошки в раскраску:

...**..
.*.*...
.***.*.
******.
*.**...

---11--
-1-2---
-111-2-
111111-
1-11---

Запустив генератор всех возможных профилей, получим что даже при M = 8 их количество P < 1000, Поэтому решение за N * P^2 укладывается по времени.

Теперь, используя профильную динамику, будем считать сколько существует полиоминошек, оканчивающихся на текущей строчке профилем p: увеличим на 1 количество у профилей в котрых каждый цвет встречается только 1 раз (например, 11-222-3); приплюсуем значения всех совместимых профилей с предыдущей строки; к глобальному счётчику, в котором насчитываем ответ, прибавим значения всех профилей, состоящих только из 1 (например, 1--111-).

Осталось обсудить самую проблемную в реализации часть решения - критерий совместимости профилей. Для этого придётся вручную рассматривать определённый набор случаев. Вот самые базовые и очевидные из них:

1)не должно встретиться квадрата 2*2 с перекрестной раскраской:
--1-
-1-1

2)Один цвет не может раздваиваться:
1111
-1-2

1--1
11-2

3)Две одноцветных группы не могут объединяться в одну:
--11-1
1-2222

Остальные случаи оставим для самостоятельного рассмотрения (всего их около 5).
Единственное отметим, что при M равном 7 или 8 появляется новый способ образования дырок в полиминошке:
1-222-1
111-111

2 1 2

1

1 8 8064

36