题目描述

你即将出售你的房子，但首先你需要确定房屋的建筑面积。这听起来可能很简单，但你有一个未使用的储藏室，你弄丢了钥匙，而且你不知道这个储藏室有多大。储藏室里唯一的东西是一个机器人吸尘器。如果你启动吸尘器并观察它最终停在哪里，也许你就能算出储藏室的大小？

储藏室由一个 $N \times M$ 的网格组成，其中 $N$ 和 $M$ 是未知的正整数。行从上到下编号为 $0$ 到 $N-1$，列从左到右编号为 $0$ 到 $M-1$。机器人有一系列指令 $s$。指令由一个包含字符 <、>、^ 和 v 的字符串描述。机器人启动后，它会读取这些指令，并根据每条指令向相应方向移动一步。如果机器人试图移出网格，它会撞到墙壁，什么也不会发生。机器人从左上角开始，即第 $0$ 行第 $0$ 列。

你会得到字符串 $s$ 以及机器人执行指令后最终所在的行和列。计算与此信息一致的 $N \cdot M$ 的最小可能值。

输入格式

第一行包含一个整数 $K$ ($1 \leq K \leq 3 \cdot 10^5$)，表示字符串 $s$ 的长度。 第二行包含字符串 $s$。 第三行包含两个整数 $r$ 和 $c$ ($0 \leq r,c < 3 \cdot 10^5$)，其中 $r$ 是机器人最终所在的行， $c$ 是机器人最终所在的列。

输出格式

输出一个整数，即 $N \cdot M$ 的最小可能值。如果没有与测试数据信息一致的 $N$ 和 $M$ 的选择，则输出 $-1$。

14
>v<v>v>^^^>>v<
1 2

8

1
>
100000 100000

-1

4
>><<
0 0

1

提示

样例解释

样例 $1$ 解释

上图展示了样例 $1$ 中最小可能的网格。机器人沿黑色曲线移动。深色方块是机器人最终的位置。

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $15$ | 机器人只向下和向右移动。 | | $2$ | $30$ | $K \le 100$| | $3$ | $20$ | $K \le 5000$ | | $4$ | $35$ | 无额外约束。 |