Kayaking

Your friend Luis is an expert kayaker planning to navigate a treacherous river. The river is modeled as a $2 \times N$ grid, completely enclosed by border cells to form a grid with $4$ rows and $N+2$ columns.

Border cells describe the surroundings of the river. Each of them is either a safe zone, like a calm eddy or the shore, represented by “.” (dot), or an obstacle, like a rock or a waterfall, represented by “#” (hash).

In each river cell, the current flows left, right, up or down, represented respectively by “<” (less-than sign), “>” (greater-than sign), “^” (caret) or “v” (lowercase letter v). Some river cells may have an unknown flow direction, represented by “?” (question mark).

A river cell is safe if following the current from that cell eventually leads to a safe zone “.”. Otherwise, the river cell is unsafe: the current hits an obstacle “#” or enters a loop within the river.

For example, consider the first sample input, where $N=2$. The top-left river cell is safe since the current flows into the safe zone on its left. The other three river cells are unsafe: the current from the bottom-left river cell leads to the obstacle directly below it, while the two river cells on the right form a loop.

A configuration of the river is obtained by assigning any of the four directions “<”, “>”, “^” or “v” to each unknown flow direction “?”; each unknown flow direction can be assigned independently of the others.

Luis needs your help to assess the river’s safety. For each integer $k$ from $0$ to $2N$ inclusive, you must determine the number of configurations having exactly $k$ safe river cells.

Input

The first line contains an integer $N$ ($1 \leq N \leq 1000$).

Each of the next $4$ lines contains a string of $N+2$ characters representing a row of the grid, as described in the statement.

Output

Output a single line with $2N+1$ integers ${C_0}, {C_1}, \ldots, {C_{2N}}$, where $C_k$ indicates the number of configurations having exactly $k$ safe river cells. Since these numbers can be large, output the remainder of dividing each of them by $998\,244\,353$.

2
##.#
.<v.
.v^.
##.#

0 1 0 0 0

1
#.#
.?.
.?.
#.#

1 0 15

2
##.#
.??.
.^<#
...#

6 4 0 0 6

4
..#..#
#>v^?.
#?<??.
#.#.#.

0 18 48 39 87 3 12 9 40

8
.########.
#????????#
#???^????#
.########.

75497471 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0