Eva loves painting. Today she is working with a square canvas of unit cells. Each cell is painted white, painted black, or empty --- not painted at all.
Eva is going to draw a black triangle inside each empty cell. She wants each triangle to be right-angled and have an area of square unit cells. Thus, there are four ways to draw a single triangle:
Each 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.
Help Eva to find out how many ways there are to finish her painting. Since the number can be large, calculate it modulo .
输入格式
The first line contains a single integer --- the side length of the canvas ().
The next lines describe the canvas from top to bottom. The -th of these lines contains characters . If , the cell in the -th row and the -th column of the canvas is painted white. If , that cell is painted black. If , that cell is empty.
输出格式
Print a single integer denoting the number of ways to finish Eva's painting, modulo .
样例
样例输入 1
2
.?
?#
样例输出 1
4
样例输入 2
3
#??
#??
?##
样例输出 2
1
样例输入 3
3
.#.
#?#
.#.
样例输出 3
0
数据范围与提示
In the first example test, there are ways to finish the painting, as illustrated below:
In the second example test, there is a single way to finish the painting:
In the third example test, regardless of how Eva draws the triangle in the center cell, it will share two sides with black squares.
