{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Иван Лукьянов\\
         Разработка: & Геннадий Короткевич\\
     \end{tabular}
}

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

Рассмотрим некоторую строку. Она состоит из закрашенных в белый или чёрный цвет клеток, а также отрезков пустых клеток между ними. Опять же, отрезки пустых клеток друг на друга не влияют, поэтому можно перемножить ответы для них.

Наконец, для отрезка пустых клеток нам важна его длина $k$, цвет клетки слева от него и цвет клетки справа от него. Если слева или справа от отрезка проходит граница поля, то будем считать, что там белая клетка. Есть четыре варианта:
\begin{itemize}
\item Если обе клетки слева и справа от отрезка~--- чёрные, то заполнить отрезок корректным образом нельзя, и можно смело выводить $0$.
\item Если клетка слева от отрезка~--- чёрная, а клетка справа~--- белая, то в каждой клетке отрезка нужно выбрать для треугольника правую сторону. Так как для отрезка есть один вариант, ответ на задачу никак не меняется.
\item Если клетка слева~--- белая, а справа~--- чёрная, то всё симметрично предыдущему случаю.
\item Если обе клетки слева и справа~--- белые, то можно выбрать любое число $x$ от $0$ до $k$ и в первых $x$ клетках отрезка выбрать для треугольника левую сторону, а в остальных $k-x$ клетках~--- правую. Следовательно, ответ на задачу нужно домножить на $k+1$.
\end{itemize}

Все последовательные отрезки пустых клеток в строках и столбцах можно найти простым линейным проходом. Сложность решения составит $O(n^2)$.