마법의 미로

매기네 반이 미로로 소풍을 갔다. 미로는 높이 $n$미터, 너비 $m$미터의 직사각형이며, 한 변이 $1 \times 1$미터인 정사각형 방 $n \times m$개로 이루어져 있다. 변을 맞댄 두 방 사이에는 한쪽 방향으로만 통하는 통로가 있다. 수리 때문에 일부 통로는 막혀 있다. 입구에서 출구에 도달할 수 있는지조차 알려지지 않았다.

입장하기 전에 매기는 각 통로의 방향과 막힌 통로가 표시된 지도를 받는다. 입구는 왼쪽 위 방이고, 출구는 오른쪽 아래 방 하나뿐이다. 지도에는 미로 안에서 영원히 맴돌 수 없다는 정보도 나와 있다. 어떤 방이든 어떤 통로로 떠나면 그 방으로 다시 돌아올 수 없다.

매기는 입구에서 출발해 미로를 지나 출구로 나가려 한다. 또 방문한 방 중 좋아하는 방 두 개의 번호를 방문한 순서대로 적는다. 같은 방을 두 번 적을 수도 있다. 미로를 빠져나가지 못하면 매기는 실망하고 아무것도 적지 않는다. 지도가 주어졌을 때, 매기가 두 번호를 적는 서로 다른 방법의 수를 구하라.

첫 줄에 공백으로 구분된 두 정수 $n$과 $m$이 주어진다 ($1 \leq n \times m \leq 500\,000$). 이어지는 $2n-1$개의 줄에 미로 지도가 주어진다.

$(2i)$번째 줄 ($1 \leq i \leq n$)은 $i$번째 행에서 이웃한 방 사이의 통로를 나타내는 길이 $m-1$의 문자열이며, 문자는 {>, <, *} 중 하나다. $j$번째 문자가 >이면 $j$번째 방에서 $j+1$번째 방으로 가는 통로가 있다. <이면 $j+1$번째 방에서 $j$번째 방으로 가는 통로가 있다. *이면 양방향 모두 통로가 없다.

$(2i+1)$번째 줄 ($1 \leq i \leq n-1$)은 $i$번째 행과 $i+1$번째 행 사이의 통로를 나타내는 길이 $m$의 문자열이며, 문자는 {v, ^, *} 중 하나다. $j$번째 문자가 v이면 $i$번째 행의 $j$번째 방에서 $i+1$번째 행의 $j$번째 방으로 가는 통로가 있다. ^이면 반대 방향 통로가 있다. *이면 양방향 모두 통로가 없다.

입구는 첫 번째 행의 첫 번째 방이고, 출구는 마지막 행의 마지막 방이다.

매기가 방문한 두 방의 번호를 방문한 순서대로 적는 방법의 수를 한 줄에 출력한다. 출구에 도달할 수 없으면 0을 출력한다.

출구에 도달하는 방법은 한 가지뿐이다. 오른쪽으로 두 번 간 다음 아래로 한 번 내려간다.