Magical Maze

Maggy's class went on an excursion to a maze. The maze is a rectangle $n$ meters high and $m$ meters wide, made of $n \times m$ square chambers of size $1 \times 1$ meter each. Between any two chambers that share a side there is a one-directional passage. Some passages are closed for repairs. It is not even known whether the exit can be reached from the entrance.

Before entering, Maggy gets a map that shows the direction of each passage and which passages are closed. The entrance is the upper left chamber, and the only exit is the bottom right chamber. The map also guarantees that you cannot loop forever in the maze: if you leave any chamber through any passage, you cannot get back to that chamber.

Maggy wants to start at the entrance, go through the maze, and leave through the exit. She also writes down the numbers of two favourite chambers she visited, in the order she visited them. One chamber may be written twice. If Maggy fails to leave the maze, she is upset and writes nothing. Given the map, count the number of different ways Maggy can write down the two numbers.

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

The $(2i)$-th line ($1 \leq i \leq n$) is a string of $m-1$ characters from the set {>, <, *}, describing the passages between consecutive chambers in the $i$-th row. If the $j$-th character is >, there is a passage from the $j$-th to the $(j+1)$-st chamber in that row. < means there is a passage from the $(j+1)$-st to the $j$-th chamber. * means there is no passage between them in either direction.

The $(2i+1)$-th line ($1 \leq i \leq n-1$) is a string of $m$ characters from the set {v, ^, *}, describing the passages between the $i$-th and $(i+1)$-st rows. If the $j$-th character is v, there is a passage from the $j$-th chamber in the $i$-th row to the $j$-th chamber in the $(i+1)$-st row. ^ means the passage goes the other way. * means there is no passage in either direction.

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

Print one integer: the number of ways Maggy can write down the numbers of two visited chambers, in the order of visiting them. If the exit cannot be reached, print 0.

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