{"scoring":null,"notes":"В первом тестовом примере есть $4$ способа закончить картину, как показано ниже:\r\n\r\n\\begin{center}\r\n\\includegraphics{pic-2.eps}\r\n\\end{center}\r\n\r\nВо втором тестовом примере есть единственный способ закончить картину:\r\n\r\n\\begin{center}\r\n\\includegraphics{pic-3.eps}\r\n\\end{center}\r\n\r\nВ третьем тестовом примере, независимо от того, как Ева нарисует треугольник в центральной ячейке, у него будут две общие стороны с черными квадратами.","legend":"Ева любит рисовать. Сегодня она работает с квадратным полотном из $n \\times n$ элементарных ячеек. Каждая ячейка окрашена в белый цвет, окрашена в черный цвет или пуста~--- не окрашена вообще.\r\n\r\nЕва нарисует черный треугольник внутри каждой пустой клетки. Она хочет, чтобы каждый треугольник был прямоугольным и имел площадь $\\frac{1}{2}$ квадратных элементарных ячеек. Таким образом, один треугольник можно нарисовать четырьмя способами:\r\n\r\n\\begin{center}\r\n\\includegraphics{pic-1.eps}\r\n\\end{center}\r\n\r\nКаждый треугольник --- это произведение искусства, и Ева хочет, чтобы их было легко отличить от остальной части картины. Для этого никакие два черных треугольника не могут иметь общую сторону друг с другом, а черный треугольник не может иметь общую сторону с черным квадратом. Обратите внимание, что два черных квадрата могут иметь общую сторону.\r\n\r\nПомогите Еве узнать, сколько существует способов закончить ее картину. Поскольку число может быть большим, вычислите его по модулю $998\\,244\\,353$.","authorLogin":"tourist","language":"russian","timeLimit":2000,"output":"Выведите единственное целое число, обозначающее количество способов закончить картину Евы по модулю $998\\,244\\,353$.","inputFile":"stdin","outputFile":"stdout","input":"Первая строка содержит единственное целое число $n$~ --- длину стороны полотна ($1 \\le n \\le 1000$).\r\n\r\nСледующие $n$ строк описывают полотно сверху вниз. $i$-я из этих строк содержит $n$ символов $s_{i, 1}, s_{i, 2}, \\ldots, s_{i, n}$. Если $s_{i, j} =$ `\\t{.}', ячейка в $i$-й строке и $j$-м столбце полотна окрашивается в белый цвет. Если $s_{i, j} =$ `\\t{\\#}', эта ячейка окрашивается в черный цвет. Если $s_{i, j} =$ `\\t{?}', эта ячейка пуста.","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":""}