CF611F New Year and Cleaning

Limak 是一只小北极熊。他的父母让他在新年前夕打扫房子。他们的家是一个有 $h$ 行 $w$ 列的矩形网格，每个单元格都是一个空方块。 由于他年纪还小，自己无法打扫房子。他打算用一个清洁机器人。 清洁机器人内置有 $n$ 步动作的指令模式，通过长度为 $n$ 的字符串给出。每一个动作（字符）会让机器人移动到四个相邻单元格之一。每个字符只能是以下四个之一："U"（上）、"D"（下）、"L"（左）、"R"（右）。每个动作耗时一分钟。 清洁机器人可以被放置并从任意一个单元格启动。然后它会重复执行它的移动模式，直到撞到墙壁（房子的四条边界之一）为止。撞到墙壁后，它可以被移动并重新启动。 Limak 不确定仅把机器人放在一个单元格能否完成打扫。因此，他打算在每一个单元格（共 $w·h$ 次）都启动机器人一次。可能有些单元格会被重复打扫，但这无妨。 Limak 有一个问题想问你。清扫整个房子总共需要多久？请你输出清扫房子所需的分钟数，结果对 $10^9+7$ 取模。如果机器人会陷入无限循环、永远停不下来的情况，则输出 $-1$。 放置和启动机器人不耗时，只有机器人撞墙时才算一分钟。详见样例说明。

第一行包含三个整数 $n$、$h$、$w$（$1 \leq n, h, w \leq 500000$），分别表示指令模式的长度、网格的行数和列数。 第二行包含长度为 $n$ 的字符串，表示机器人的移动模式。每个字符仅能为大写字母 'U'、'D'、'L' 或 'R' 之一。

输出一行答案。 如果机器人会永远不停下，请输出 $-1$。否则，输出清扫整个房子的分钟数，结果对 $10^9+7$ 取模。

在第一个样例中，房间是一个 $10$ 行 $2$ 列的网格。从第二列的任何一个格子启动机器人，只需要一步（即一分钟）机器人就会撞墙——因为它尝试向右走但没有第 $3$ 列。从第一列的任何一个格子启动则需要两步。总的分钟数为 $10·1+10·2=30$。 在第二个样例中，机器人总会按照 "RULRULRULR..." 的模式移动。例如，从第二行最左边的单元格启动时，机器人在撞到上壁前会移动 $5$ 步。 由 ChatGPT 5 翻译