Maggy 的班级去迷宫远足了！这个迷宫呈长方形，高为 $n$ 米，宽为 $m$ 米，由 $n \cdot m$ 个大小为 $1 \times 1$ 米的正方形房间组成。在每两个相邻（共享一条边）的房间之间有一条单向通道。由于维修，其中一些通道被关闭了。事实上，甚至无法确定是否能从入口到达出口。

在进入迷宫之前，Maggy 得到了一张迷宫地图。它包含了通道的方向以及关于关闭通道的信息。地图还显示，迷宫的入口通往地图左上角的房间，而唯一的出口位于地图右下角的房间。此外，还有信息表明你不能在迷宫内无限循环：如果你通过任何通道离开任何房间，都不可能再回到这个房间。

Maggy 想要从入口出发，穿过迷宫并从出口离开。她还想按她访问它们的顺序，写下她在迷宫中访问过的两个最喜欢的房间的编号；也许她会非常喜欢其中一个房间，以至于把它写下两次。如果 Maggy 没能离开迷宫，她会很沮丧，并且什么都不会写。给出迷宫的地图，计算 Maggy 有多少种不同的方式可以写下这两个编号。

输入格式

输入的第一行包含两个由单个空格分隔的整数 $n$ 和 $m$（$1 \le n \cdot m \le 500\,000$），分别表示迷宫的高度和宽度。接下来的 $2n - 1$ 行包含迷宫的地图。

在第 $2i-1$ 行（$1 \le i \le n$）中，有一个由字符集 $\{>, <, *\}$ 中的 $m - 1$ 个字符组成的字符串，描述地图第 $i$ 行中相邻房间之间的通道：如果字符串中的第 $j$ 个字符是 >，则存在一条从第 $i$ 行第 $j$ 个房间到第 $(j + 1)$ 个房间的通道；< 表示存在一条从第 $i$ 行第 $(j + 1)$ 个房间到第 $j$ 个房间的通道；而 * 表示这两个房间之间在任一方向上都没有通道。

类似地，在第 $2i$ 行（$1 \le i \le n-1$）中，有一个由字符集 $\{v, \wedge, *\}$ 中的 $m$ 个字符组成的字符串，描述地图第 $i$ 行和第 $i + 1$ 行房间之间的通道：如果第 $j$ 个字符是 v，则存在一条从第 $i$ 行第 $j$ 个房间到第 $i + 1$ 行第 $j$ 个房间的通道；^ 表示存在一条从第 $i + 1$ 行第 $j$ 个房间到第 $i$ 行第 $j$ 个房间的通道；而 * 表示第 $i$ 行和第 $i + 1$ 行的第 $j$ 个房间之间在任一方向上都没有通道。

迷宫的入口通往第一行第一个房间，出口在最后一行最后一个房间。

输出格式

你应该在输出的第一行也是唯一一行中写入一个整数——Maggy 按访问顺序写下她访问过的两个（不一定相同）房间编号的可能方式的数量。

如果无法到达出口，则应输出 0。

样例

输入格式 1

2 3
>>
*^v
<>

输出格式 1

10

说明

只有一种方法可以到达出口：先向右走两次，然后向下走一次。