23614번 - Magical Maze 다국어

Maggy's class went on an excursion to a maze! The maze has the shape of a rectangle of height $n$ and width $m$ meters and consists of $n \cdot m$ square chambers, each of size $1 \times 1$ meter. There is one-directional passage between every two chambers that share a side. Due to repairs some of those passages are closed. In fact, it is not even known whether it is possible to reach the exit from the entrance.

Maggy was given a map of the maze before entering it. It contains the directions of the passages as well as the information about the closed passages. The map also shows that the entrance to the maze leads to the chamber in the upper left corner of the map and the only exit is in the chamber in the bottom right corner of the map. There is also an information that you cannot loop forever inside the maze: if you leave any chamber with any passage, it is not possible to get back to this chamber.

Maggy wants to start at the entrance, go through the maze and leave by the exit. She also wants to write down the numbers of two favourite chambers of the maze that she has visited, in the order in which she has seen them; perhaps she will like one of the chambers so much that she will write it down twice. If Maggy fails to leave the maze she will be upset and will not write down anything. Given the map of the maze, compute in how many different ways Maggy can write down those two numbers.

The first line of the input contains two integers $n$ and $m$ ($ 1 \leq n \cdot m \leq 500\,000$) separated by a single space, denoting the height and width of the maze, respectively. The following $2n-1$ lines contain the map of the maze.

In the $(2i)$-th line ($1 \leq i \leq n$) there is a string of $m-1$ characters from the set {>, <, *}, describing the passages between consecutive chambers in the $i$-th row of the map: if the $j$-th character in the string is > then there is a passage from the $j$-th to the $(j+1)$-st chamber in the $i$-th row; < means that there is a passage from the $(j + 1)$-st to the $j$-th chamber in the $i$-th row; while * denotes that there is no passage between these two chambers, in either direction.

Similarly, in the line $2i + 1$ ($ 1 \leq i \leq n-1 $) there is a string of $m$ characters from the set {v, ^, *}, describing the passages between the chambers in the $i$-th and $(i+1)$-st rows of the map: if the $j$-th character is v then there is a passage from the $j$-th chamber in the $i$-th row to the $j$-th chamber  in $(i+1)$-st row, ^ means that there is a passage from the $j$-th chamber in $(i+1)$-st row to the $j$-th chamber in the $i$-th row, and * denotes that there is no passage between the $j$-th chambers in the $i$-th and $(i+1)$-st row, in either direction.

The entrance to the maze leads to the first chamber in the first row, and the exit is in the last chamber in the last row.

You should write one integer in the first and only line of the output -- the number of possible ways in which Maggy can write down the numbers of two (not necessarily different) visited chambers, in the order of visiting them.

If it is not possible to reach the exit, then you should write $0$.

There is only one way to reach the exit: first go right twice and then once down.