CF611F.New Year and Cleaning

Limak is a little polar bear. His parents told him to clean a house before the New Year's Eve. Their house is a rectangular grid with h rows and w columns. Each cell is an empty square.

He is a little bear and thus he can't clean a house by himself. Instead, he is going to use a cleaning robot.

A cleaning robot has a built-in pattern of n moves, defined by a string of the length n. A single move (character) moves a robot to one of four adjacent cells. Each character is one of the following four: 'U' (up), 'D' (down), 'L' (left), 'R' (right). One move takes one minute.

A cleaning robot must be placed and started in some cell. Then it repeats its pattern of moves till it hits a wall (one of four borders of a house). After hitting a wall it can be placed and used again.

Limak isn't sure if placing a cleaning robot in one cell will be enough. Thus, he is going to start it w·h times, one time in each cell. Maybe some cells will be cleaned more than once but who cares?

Limak asks you one question. How much time will it take to clean a house? Find and print the number of minutes modulo 109 + 7. It's also possible that a cleaning robot will never stop — then print "-1" (without the quotes) instead.

Placing and starting a robot takes no time, however, you must count a move when robot hits a wall. Take a look into samples for further clarification.

Limak 是一只小北极熊。他的父母让他在除夕夜之前打扫房子。他们的房子是一个有 $h$ 行和 $w$ 列的矩形网格，每个格子都是一个空的正方形。

由于 Limak 还是一只小熊，他无法独自完成打扫任务。因此，他将使用一台清洁机器人。

这台清洁机器人内置了一个长度为 $n$ 的移动模式，由一个长度为 $n$ 的字符串定义。每次移动（即字符串中的一个字符）会使机器人向四个相邻格子之一移动。每个字符是以下四种之一：'U'（向上）、'D'（向下）、'L'（向左）、'R'（向右）。每次移动耗时一分钟。

清洁机器人必须被放置并启动于某个格子中。随后，它会不断重复执行其移动模式，直到撞到墙壁（即房子四条边界之一）为止。撞墙后，该机器人可被再次放置并重新使用。

Limak 不确定仅在某一个格子中启动一次清洁机器人是否足够。因此，他将在全部 $w \cdot h$ 个格子中各启动一次机器人（即每个格子恰好启动一次）。某些格子可能会被多次清洁，但这并不重要。

Limak 向你提出一个问题：打扫完整座房子总共需要多少时间？请计算并输出总分钟数对 $10^9 + 7$ 取模的结果。另外，也存在清洁机器人永远无法停止（即永远不会撞墙）的情况；此时请输出 -1（不带引号）。

放置并启动机器人本身不消耗时间，但当机器人撞墙时，该次撞墙的移动仍需计入时间。请参考样例以进一步理解。

The first line contains three integers n, h and w (1 ≤ n, h, w ≤ 500 000) — the length of the pattern, the number of rows and the number of columns, respectively.

The second line contains a string of length n — the pattern of n moves. Each character is one of uppercase letters 'U', 'D', 'L' or 'R'.

第一行包含三个整数 $n$、$h$ 和 $w$（$1 ≤ n, h, w ≤ 500\,000$），分别表示模式的长度、行数和列数。

第二行包含一个长度为 $n$ 的字符串——表示 $n$ 次移动的模式。每个字符均为大写字母 'U'、'D'、'L' 或 'R' 之一。

Print one line with the answer.

If a cleaning robot will never stop, print "-1" (without the quotes). Otherwise, print the number of minutes it will take to clean a house modulo 109 + 7.

输出一行答案。

如果清洁机器人永远不会停止，则输出 -1（不带引号）。否则，输出清洁房屋所需的分钟数对 $10^9 + 7$ 取模的结果。

In the first sample house is a grid with 10 rows and 2 columns. Starting a robot anywhere in the second column will result in only one move (thus, one minute of cleaning) in which robot will hit a wall — he tried to go right but there is no third column. Starting a robot anywhere in the first column will result in two moves. The total number of minutes is 10·1 + 10·2 = 30.

In the second sample a started robot will try to move "RULRULRULR..." For example, for the leftmost cell in the second row robot will make 5 moves before it stops because of hitting an upper wall.

在第一个样例中，房屋是一个 10 行 2 列的网格。若将机器人起始位置设在第二列的任意格子，则机器人仅能执行一次移动（即仅需 1 分钟清洁时间），随后便会撞墙——因为它试图向右移动，但并不存在第三列。若将机器人起始位置设在第一列的任意格子，则机器人将执行两次移动。总耗时为 $10 \cdot 1 + 10 \cdot 2 = 30$ 分钟。

在第二个样例中，启动后的机器人将尝试按 “RULRULRULR...” 的模式移动。例如，对于第二行最左侧的格子，机器人将在撞到上侧墙壁后停止，共执行 5 次移动。