{"scoring":null,"notes":"In the first example test, there are $4$ ways to finish the painting, as illustrated below:\r\n\r\n\\begin{center}\r\n\\includegraphics{pic-2.eps}\r\n\\end{center}\r\n\r\nIn the second example test, there is a single way to finish the painting:\r\n\r\n\\begin{center}\r\n\\includegraphics{pic-3.eps}\r\n\\end{center}\r\n\r\nIn the third example test, regardless of how Eva draws the triangle in the center cell, it will share two sides with black squares.\r\n\r\n","legend":"Eva loves painting. Today she is working with a square canvas of $n \\times n$ unit cells. Each cell is painted white, painted black, or empty~--- not painted at all.\r\n\r\nEva is going to draw a black triangle inside each empty cell. She wants each triangle to be right-angled and have an area of $\\frac{1}{2}$ square unit cells. Thus, there are four ways to draw a single triangle:\r\n\r\n\\begin{center}\r\n\\includegraphics{pic-1.eps}\r\n\\end{center}\r\n\r\nEach triangle is a piece of art, and Eva wants them to be easily distinguishable from the rest of the painting. To achieve that, no two black triangles may share a common side with each other, and no black triangle may share a common side with a black square. Note that two black squares are allowed to share a common side.\r\n\r\nHelp Eva to find out how many ways there are to finish her painting. Since the number can be large, calculate it modulo $998\\,244\\,353$.","authorLogin":"tourist","language":"english","timeLimit":2000,"output":"Print a single integer denoting the number of ways to finish Eva's painting, modulo $998\\,244\\,353$.","inputFile":"stdin","outputFile":"stdout","input":"The first line contains a single integer $n$~--- the side length of the canvas ($1 \\le n \\le 1000$).\r\n\r\nThe next $n$ lines describe the canvas from top to bottom. The $i$-th of these lines contains $n$ characters $s_{i, 1}, s_{i, 2}, \\ldots, s_{i, n}$. If $s_{i, j} =$ `\\t{.}', the cell in the $i$-th row and the $j$-th column of the canvas is painted white. If $s_{i, j} =$ `\\t{\\#}', that cell is painted black. If $s_{i, j} =$ `\\t{?}', that cell is empty.","authorName":"Gennady Korotkevich","sampleTests":[{"output":"4\r\n","input":"2\r\n.?\r\n?#\r\n","inputFile":"example.01","outputFile":"example.01.a"},{"output":"1\r\n","input":"3\r\n#??\r\n#??\r\n?##\r\n","inputFile":"example.02","outputFile":"example.02.a"},{"output":"0\r\n","input":"3\r\n.#.\r\n#?#\r\n.#.\r\n","inputFile":"example.03","outputFile":"example.03.a"}],"name":"Easily Distinguishable Triangles","interaction":null,"memoryLimit":536870912,"tutorial":"{\r\n    \\parindent=1cm\r\n    \\begin{tabular}{l@{\\extracolsep{1cm}}l}\r\n         Идея: & Иван Лукьянов\\\\\r\n         Разработка: & Геннадий Короткевич\\\\\r\n     \\end{tabular}\r\n}\r\n\r\nДля того, чтобы нарисовать треугольник в пустой клетке, нам нужно выбрать из левой и правой границ клетки, а также из верхней и нижней, причём эти выборы друг на друга не влияют. Поэтому можно решать задачу отдельно для каждой строки матрицы и отдельно для каждого столбца, а потом перемножить.\r\n\r\nРассмотрим некоторую строку. Она состоит из закрашенных в белый или чёрный цвет клеток, а также отрезков пустых клеток между ними. Опять же, отрезки пустых клеток друг на друга не влияют, поэтому можно перемножить ответы для них.\r\n\r\nНаконец, для отрезка пустых клеток нам важна его длина $k$, цвет клетки слева от него и цвет клетки справа от него. Если слева или справа от отрезка проходит граница поля, то будем считать, что там белая клетка. Есть четыре варианта:\r\n\\begin{itemize}\r\n\\item Если обе клетки слева и справа от отрезка~--- чёрные, то заполнить отрезок корректным образом нельзя, и можно смело выводить $0$.\r\n\\item Если клетка слева от отрезка~--- чёрная, а клетка справа~--- белая, то в каждой клетке отрезка нужно выбрать для треугольника правую сторону. Так как для отрезка есть один вариант, ответ на задачу никак не меняется.\r\n\\item Если клетка слева~--- белая, а справа~--- чёрная, то всё симметрично предыдущему случаю.\r\n\\item Если обе клетки слева и справа~--- белые, то можно выбрать любое число $x$ от $0$ до $k$ и в первых $x$ клетках отрезка выбрать для треугольника левую сторону, а в остальных $k-x$ клетках~--- правую. Следовательно, ответ на задачу нужно домножить на $k+1$.\r\n\\end{itemize}\r\n\r\nВсе последовательные отрезки пустых клеток в строках и столбцах можно найти простым линейным проходом. Сложность решения составит $O(n^2)$."}